Table of Contents
Reverse Linked List II
This question came in Arista technical interview..
Logic
- Problem is not with reversing the list but after reversing the list, original list is also getting changed for right most index.
- Edge cases are very tricky, if head or tail are part of input
- Visualisation of how pointer manipulation can be done is very important.
From Pen and Paper
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, leftIndex int, rightIndex int) *ListNode {
//edge case
if leftIndex == rightIndex {
return head
}
var leftPrev *ListNode
current := head
//input is started from 1
// so use staring point as 1 to make it simple in iterations
for i := 1; i <= leftIndex-1; i++ {
leftPrev = current
current = current.Next
}
oldLeftHead := current
//fmt.Printf("oldLeftHead=%d\n", oldLeftHead.Val)
var prev *ListNode
for j := 1; j <= rightIndex-leftIndex+1; j++ {
next := current.Next
current.Next = prev
prev = current
current = next
}
oldLeftHead.Next = current
if leftPrev == nil {
return prev
}
leftPrev.Next = prev
return head
}
Golang Code Attempt-1
package main
import "fmt"
type Node struct {
Val int
Next *Node
}
func printList(head *Node) {
temp := head
for temp != nil {
fmt.Printf("%d ", temp.Val)
temp = temp.Next
}
fmt.Println()
}
func findNode(head *Node, index int) (current, prev, next *Node) {
temp := head
count := 1
for temp != nil && count < index {
prev = temp
temp = temp.Next
count++
}
current = temp
if current != nil {
next = current.Next
}
return current, prev, next
}
/*
func reverse(head *Node) *Node {
var prev *Node
current := head
for current != nil {
next := current.Next
current.Next = prev
prev = current
current = next
}
newhead := prev
newTail := head
fmt.Println()
fmt.Printf("newhead=%d\n", newhead.Val)
fmt.Printf("newTail=%d\n", newTail.Val)
return prev
}*/
func reverseCustom(root, leftNode, rightNode, leftPrev, rightNext *Node) *Node {
if leftNode == rightNode {
return root
}
var prev *Node
head := leftNode
current := head
for current != nil && prev != rightNode {
next := current.Next
current.Next = prev
prev = current
current = next
}
newhead := prev
newTail := head
fmt.Println("\nPrinting new linked list with newhead")
printList(newhead)
fmt.Println()
//newhead = 4
//newTail = 2
//leftPrev = 1
//rightNext = 5
if leftPrev != nil {
leftPrev.Next = newhead
}
if rightNext != nil {
newTail.Next = rightNext
}
if leftPrev != nil {
return root
}
if leftPrev == nil || rightNext == nil {
return newhead
}
return root
}
func main() {
//values := []int{1,2,3,4,5}
first := &Node{
Val: 1,
}
two := &Node{
Val: 2,
}
third := &Node{
Val: 3,
}
four := &Node{
Val: 4,
}
five := &Node{
Val: 5,
}
four.Next = five
third.Next = four
two.Next = third
first.Next = two
head := first
fmt.Println("\nBefore reversing linked list")
printList(head)
//leftIndex, rightIndex := 2, 5
//leftIndex, rightIndex := 1, 4
//leftIndex, rightIndex := 1, 5
//leftIndex, rightIndex := 2, 4
leftIndex, rightIndex := 3, 3
fmt.Println()
fmt.Printf("leftIndex=%d, rightIndex=%d\n", leftIndex, rightIndex)
leftNode, leftPrev, leftNext := findNode(head, leftIndex)
if leftPrev != nil {
fmt.Printf("leftIndex=%d, leftNode=%#v, leftPrev=%#v\n", leftIndex, leftNode.Val, leftPrev.Val)
}
if leftNext != nil {
fmt.Printf("leftIndex=%d, leftNode=%#v, leftNext=%#v\n", leftIndex, leftNode.Val, leftNext.Val)
}
rightNode, rightPrev, rightNext := findNode(head, rightIndex)
if rightPrev != nil {
fmt.Printf("rightIndex=%d, rightNode=%#v, rightPrev=%#v\n", rightIndex, rightNode.Val, rightPrev.Val)
}
if rightNext != nil {
fmt.Printf("rightIndex=%d, rightNode=%#v, rightNext=%#v\n", rightIndex, rightNode.Val, rightNext.Val)
}
// Reverse list
//head = reverse(head)
//head = reverse(head)
// Reverse list
fmt.Println("\nStarting custom reverse reversing linked list")
head = reverseCustom(head, leftNode, rightNode, leftPrev, rightNext)
fmt.Println("\nAfter reversing linked list")
printList(head)
}Golang Code Attempt-2 Better Version
package main
import "fmt"
type Node struct {
Val int
Next *Node
}
func printList(head *Node) {
for temp := head; temp != nil; temp = temp.Next {
fmt.Printf("%d ", temp.Val)
}
fmt.Println()
}
func findNode(head *Node, index int) (current, prev, next *Node) {
temp := head
count := 1
for temp != nil && count < index {
prev = temp
temp = temp.Next
count++
}
current = temp
if current != nil {
next = current.Next
}
return current, prev, next
}
func reverseCustom(root, leftNode, rightNode, leftPrev, rightNext *Node) *Node {
// Edge case: no need to reverse if leftNode == rightNode
if leftNode == rightNode {
return root
}
var prev *Node
current := leftNode
for current != rightNext {
next := current.Next
current.Next = prev
prev = current
current = next
}
// Update pointers
if leftPrev != nil {
leftPrev.Next = prev
} else {
root = prev
}
leftNode.Next = rightNext
return root
}
func main() {
// Construct the linked list
first := &Node{Val: 1}
two := &Node{Val: 2}
third := &Node{Val: 3}
four := &Node{Val: 4}
five := &Node{Val: 5}
four.Next = five
third.Next = four
two.Next = third
first.Next = two
head := first
fmt.Println("Before reversing linked list:")
printList(head)
leftIndex, rightIndex := 2, 4
fmt.Printf("\nleftIndex=%d, rightIndex=%d\n", leftIndex, rightIndex)
leftNode, leftPrev, _ := findNode(head, leftIndex)
rightNode, _, rightNext := findNode(head, rightIndex)
head = reverseCustom(head, leftNode, rightNode, leftPrev, rightNext)
fmt.Println("\nAfter reversing linked list:")
printList(head)
}Output
head = [1,2,3,4,5], left = 2, right = 4
Output
[1,4,3,2,5]
Please visit https: https://codeandalgo.com for more such contents
Leave a Reply