Question

Formatted question description: https://leetcode.ca/all/92.html

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Follow up: Could you do it in one pass?

Algorithm

Take the example in the title, the three points that are transformed are 2, 3, and 4. We need to find the first node before the transformation node, as long as the pre is moved backward by m-1 steps.

Why do you want to subtract 1, because the problem is counting from 1, here only one step is taken, which is node 1, and use pre to point to it. What if the node 1 starts to change? This is why we use the dummy node. Pre can also point to the dummy node. Then the exchange is about to begin. Since only two nodes can be exchanged at a time, we follow the exchange sequence as follows:

-> 2 -> 3 -> 4 -> 5 -> NULL

-> 3 -> 2 -> 4 -> 5 -> NULL

-> 4 -> 3 -> 2 -> 5 -> NULL

This problem is a follow-up problem for problem 206. In this problem, only the nodes from position m to n should be reversed, and the reverse operation should be done in one-pass. The iterative solution for problem 206 can be adapted here, with some modification.

Obviously, if the list is null, or there is only one element in the list, or position m is the same as position n, then no reverse needs to be done and just return the original list.

Since the head may also be reversed, create a dummyHead whose next pointer points to head. Find the reverse start node, the reverse end node, the last node before reverse and the first node after reverse, and then do the reverse operation.

For example, for linked list 1->2->3->4->5->NULL, m = 2, n = 4, the reverse start node is 2, the reverse end node is 4, the last node before reverse is 1, and the first node after reverse is 5.

Like the iterative solution for problem 206, use two pointers prev and curr to do the iteration. After the loop, set the last node before reverse to point to the reverse end node (which is the start of the reverse part after reverse), and set the reverse start node (which is the end of the reverse part after reverse) to point to the first node after reverse.

Finally, return dummyHead.next.

Code

import java.util.Stack;

public class Reverse_Linked_List_II {

	/**
	 * Definition for singly-linked list.
	 * public class ListNode {
	 *     int val;
	 *     ListNode next;
	 *     ListNode(int x) { val = x; }
	 * }
	 */

	public class Solution_optimize {
	    public ListNode reverseBetween(ListNode head, int m, int n) {

	        ListNode dummy = new ListNode(0);
	        ListNode prev = dummy;

	        // I missed this one
	        prev.next = head;

	        ListNode p = head;

	        for (int i = 1; i < m; i++) {
	            prev = p;
	            p = p.next;
	        }

	        // @note:@memorize: now p is pointing to m-th node
	        ListNode originalFirst = p;
	        for (int i = m; i < n; i++) {
	            ListNode currentHead = prev.next;
	            ListNode futureHead = originalFirst.next;

	            // swap
	            // prev.next = currentHead.next;
	            prev.next = futureHead;
	            // currentHead.next = futureHead.next;
	            originalFirst.next = futureHead.next;
	            futureHead.next = currentHead;
	        }

	        return dummy.next;
	    }
	}


	public class Solution {
	    public ListNode reverseBetween(ListNode head, int m, int n) {

	    	if (m > n) {
	        	return reverseBetween(head, n, m);
	        }

	    	int diff = n - m;
	    	if (diff == 0) {
	    		return head;
	    	}

	    	ListNode p1 = head;

	    	// set diff for both pointers
	    	// @note: corner case: n-m > list-length
	    	while (diff > 0 && p1 != null) {
	    		p1 = p1.next;
	    		diff--;
	    	}

	    	ListNode dummy = new ListNode(0);
	    	dummy.next = head;

	    	ListNode prev = dummy;
	    	ListNode p2 = head;

	    	int mm = m;
	    	while (mm - 1> 0) {
	    		prev = prev.next;
	    		p1 = p1.next;
	    		p2 = p2.next;

	    		mm--;
	    	}

	    	ListNode nextRecord = p1.next;
	    	diff = n - m;

	    	// start reverse from p1 to p2
	    	// 1->2->3->4->5
	    	Stack<ListNode> sk = new Stack<>();
	    	while (p2 != p1.next) { // @note: here, when p1==p2 should enter loop
	    		sk.push(p2);
	    		p2 = p2.next;
	    	}

	    	while (!sk.isEmpty()) {
	    		prev.next = sk.pop();
	    		prev = prev.next;
	    	}

	    	prev.next = nextRecord;

	    	return dummy.next;
	    }
	}
}

############

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head.next == null || left == right) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; ++i) {
            pre = pre.next;
        }
        ListNode p = pre;
        ListNode q = pre.next;
        ListNode cur = q;
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        p.next = pre;
        q.next = cur;
        return dummy.next;
    }
}

// OJ: https://leetcode.com/problems/reverse-linked-list-ii/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode dummy, *p = &dummy;
        dummy.next = head;
        for (int i = 1; i < m; ++i) p = p->next;
        auto q = p->next, tail = q;
        for (int i = m; i <= n; ++i) {
            auto node = q;
            q = q->next;
            node->next = p->next;
            p->next = node;
        }
        tail->next = q;
        return dummy.next;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        if head.next is None or left == right:
            return head
        dummy = ListNode(0, head)
        pre = dummy
        for _ in range(left - 1):
            pre = pre.next
        p, q = pre, pre.next
        cur = q
        # +1, so when for loop done, 'cur' is at right's next node
        for _ in range(right - left + 1):
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        p.next = pre
        # p,q did not change by the for loop, but now pre at right(or called m) node, cur at right+1 node
        q.next = cur
        return dummy.next

############

class Solution_optimize:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        dummy = ListNode(0)
        prev = dummy
        prev.next = head
        p = head

        for i in range(1, m):
            prev = p
            p = p.next

        original_first = p # this is anchor node always pointing to the next-to-be-swapped
        for i in range(m, n):
            current_head = prev.next
            future_head = original_first.next
            
            prev.next = future_head
            original_first.next = future_head.next
            future_head.next = current_head

        return dummy.next

############

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
  def reverseBetween(self, head, m, n):
    """
    :type head: ListNode
    :type m: int
    :type n: int
    :rtype: ListNode
    """

    def reverse(root, prep, k):
      cur = root
      pre = None
      next = None
      while cur and k > 0:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next
        k -= 1
      root.next = next
      prep.next = pre
      return pre

    dummy = ListNode(-1)
    dummy.next = head
    k = 1
    p = dummy
    start = None
    while p:
      if k == m:
        start = p
      if k == n + 1:
        reverse(start.next, start, n - m + 1)
        return dummy.next
      k += 1
      p = p.next

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head.Next == nil || left == right {
		return head
	}
	dummy := &ListNode{0, head}
	pre := dummy
	for i := 0; i < left-1; i++ {
		pre = pre.Next
	}
	p, q := pre, pre.Next
	cur := q
	for i := 0; i < right-left+1; i++ {
		t := cur.Next
		cur.Next = pre
		pre = cur
		cur = t
	}
	p.Next = pre
	q.Next = cur
	return dummy.Next
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseBetween(
    head: ListNode | null,
    left: number,
    right: number,
): ListNode | null {
    const n = right - left;
    if (n === 0) {
        return head;
    }

    const dummy = new ListNode(0, head);
    let pre = null;
    let cur = dummy;
    for (let i = 0; i < left; i++) {
        pre = cur;
        cur = cur.next;
    }
    const h = pre;
    pre = null;
    for (let i = 0; i <= n; i++) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    h.next.next = cur;
    h.next = pre;
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
    if (!head.next || left == right) {
        return head;
    }
    const dummy = new ListNode(0, head);
    let pre = dummy;
    for (let i = 0; i < left - 1; ++i) {
        pre = pre.next;
    }
    const p = pre;
    const q = pre.next;
    let cur = q;
    for (let i = 0; i < right - left + 1; ++i) {
        const t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    p.next = pre;
    q.next = cur;
    return dummy.next;
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseBetween(ListNode head, int left, int right) {
        if (head.next == null || left == right) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy;
        for (int i = 0; i < left - 1; ++i) {
            pre = pre.next;
        }
        ListNode p = pre;
        ListNode q = pre.next;
        ListNode cur = q;
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        p.next = pre;
        q.next = cur;
        return dummy.next;
    }
}

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn reverse_between(head: Option<Box<ListNode>>, left: i32, right: i32) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        let mut pre = &mut dummy;
        for _ in 1..left {
            pre = &mut pre.as_mut().unwrap().next;
        }
        let mut cur = pre.as_mut().unwrap().next.take();
        for _ in 0..right - left + 1 {
            let mut next = cur.as_mut().unwrap().next.take();
            cur.as_mut().unwrap().next = pre.as_mut().unwrap().next.take();
            pre.as_mut().unwrap().next = cur.take();
            cur = next;
        }
        for _ in 0..right - left + 1 {
            pre = &mut pre.as_mut().unwrap().next;
        }
        pre.as_mut().unwrap().next = cur;
        dummy.unwrap().next
    }
}

92 - Reverse Linked List II

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions