Golang simple solution in 1 pass iterative manner


  • 0

    Illustration:

    [a] -> [b] -> [c] -> [d] -> [e]
    
    If we want to reverse from b to d, the result would be:
    
     ┌─────────────────↓
    [a] [b] <- [c] <- [d] [e]
       └─────────────────↑
    

    So we must simply reverse nodes from m to n, while remember the left side of m th node and right side of n th node (we call this respectively left and right). If left exists, we need to connect the left 's Next to n th node.
    Also we need to connect the m th node's Next to the right node.

    And one thing tricky is, if left doesn't exist, actually n th node should be the new head, so we need to assign head to n th head.

    func reverseBetween(head *ListNode, m int, n int) *ListNode {
    	if head == nil || head.Next == nil || m == n {
    		return head
    	}
    
    	var left, right, start, prev, cur, next *ListNode
    	cur = head
    	next = cur.Next
    
    	i := 1
    	for { // iterate until m
    		if i == m {
    			break
    		}
    		i++
    		prev = cur
    		cur = next
    		next = next.Next
    	}
    
    	left, start = prev, cur
    	for { // reverse m to n
    		if i > n {
    			break
    		}
    		i++
    		cur.Next = prev
    		prev = cur
    		cur = next
    		if next != nil {
    			next = next.Next
    		}
    	}
    	right = cur
    
    	// connect left, right and adjust head
    	if left == nil {
    		head = prev
    	} else {
    		left.Next = prev
    	}
    	start.Next = right
    	return head
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.