92. Reverse Linked List II #

Problem #

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Problem Summary #

Given the positions m and n of 2 nodes in a linked list, reverse all nodes within the interval between these two positions.

Solution Approach #

Since the entire linked list may be reversed, construct a new head node pointing to the current head. The subsequent processing method is: find the node p before the first node that needs to be reversed. Starting from this node, insert the following nodes one by one after node p using the “head insertion” method. Use n-m to control the number of loop iterations.

In this problem, nodes can be changed in place; it is enough to modify the next pointers of each node. No cursor pointer p is needed. Because after each reversal, the relative positions of the original nodes change, which is equivalent to the cursor pointer having already moved, so there is no need for another operation like p = p.Next.

Code #

package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseBetween(head *ListNode, m int, n int) *ListNode {
	if head == nil || m >= n {
		return head
	}
	newHead := &ListNode{Val: 0, Next: head}
	pre := newHead
	for count := 0; pre.Next != nil && count < m-1; count++ {
		pre = pre.Next
	}
	if pre.Next == nil {
		return head
	}
	cur := pre.Next
	for i := 0; i < n-m; i++ {
		tmp := pre.Next
		pre.Next = cur.Next
		cur.Next = cur.Next.Next
		pre.Next.Next = tmp
	}
	return newHead.Next
}