Question

link

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.

Stats

Frequency 2
Difficulty 3
Adjusted Difficulty 3
Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very standard interview question of LinkedList.

Solution

Keep 2 pointers, one of which points to preReversePosition, another one points to finalTailOfTheReversedPart. Each time, I will get next element and insert it between the 2 pointers mentioned above. See below image for details:

The coding isn’t easy, there can be a lot of details being omitted. Just think of it in this way: in the above picture, 123 is broken away from 45678. Each time, get next element from 45678, and insert it right after 2. Do this 2 times, so that 4,5 are moved. In the end, make 3 point to 6, and solution done.

Code

First, my code

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode preHead = new ListNode(0);
    preHead.next = head;
    ListNode before = preHead;
    for (int i = 1; i < m; i ++)
        before = before.next;
    ListNode rTail = before.next;
    ListNode cur = before.next.next;
    for (int i = 0; i < n - m; i ++) {
        ListNode temp = cur.next;
        cur.next = before.next;
        before.next = cur;
        cur = temp;
    }
    rTail.next = cur;
    return preHead.next;
}

**Second, **

A lot of people have similar solutions, so I won’t post any of their code. Reading it won’t help, write it yourself is actually important.

A lot of people have complained about this problem not easy to write.