LeetCode Reverse Linked List II: One Pass

Overview

LeetCode Reverse Linked List II tests pointer manipulation. In one pass, the sub-list over m to n can be reversed in a single loop without post processing.

LeetCode Reverse Linked List II Problem

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

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 <= m <= n <= length of list.

Solution to Reverse in One Pass

No tricky algorithm here, it is just test your ability to use pointers well. Be careful when dealing with some border cases or NULL pointers. Just simulate the process of doing the reversing: use several pointers, scan through the list, when arrive the m-th node, start reversing until the n-th node, and concatenate this revered sub list with the other possible two remaining parts of the original list. Be extremely careful about special cases which might lead to NULL pointers. The following source code is quite elegant and simple but a bit hard to be understood intuitively, it is accepted by LeetCode OJ to pass this Reverse Linked List II problem:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(
                    ListNode *head,
                    int m, int n) {
        if (NULL == head ||
            NULL == head->next ||
            m >= n) {
            return head;
        }

        n -= m;
        ListNode s(0);
        s.next = head;

        ListNode *p1 = &s;
        while (--m)
            p1 = p1->next;
        ListNode *p2 = p1->next;
        ListNode *p3 = p2->next;

        while (n--) {
            p3 = p2->next;
            p2->next = p3->next;
            p3->next = p1->next;
            p1->next = p3;
        }
        return s.next;
    }
};

The following Java code might be easier to understand, and it is accepted by LeetCode OJ to pass this Reverse Linked List II problem as well:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
   public ListNode reverseBetween(
                       ListNode head,
                       int m, int n) {
	if (m >= n ||
            head == null ||
            head.next == null) {
		return head;
	}

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

	ListNode lt, rh, p1, p2, p3;
	p1 = s;
	p2 = head;
	p3 = p2.next;

	for (int i = 1; i < m; ++i) {
		p1 = p2;
		p2 = p3;
		p3 = p2.next;
	}

	lt = p1;

	for (int i = m; i < n; ++i) {
		p1 = p2;
		p2 = p3;
		p3 = p2.next;

		p2.next = p1;
	}

	rh = p3;
	lt.next.next = rh;
	lt.next = p2;

	return s.next;
    }
}

Note:

  1. And regarding with the time/space complexity, the above implementation takes O(n) time and O(1) space with a single pass over the linked list.
  2. This problem is a generalized version of this problem: LeetCode Reverse Linked List: Recursive VS Iterative Solution , you can take a look at that as well

Summary

LeetCode Reverse Linked List II tests pointer manipulation. In one pass, the sub-list over m to n can be reversed in a single loop without post processing.

Written on May 20, 2013