Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 92] Reverse Linked List II



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.

Given m, n satisfy the following condition:
1 ≤ mn ≤ length of list.


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

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


This is a very standard interview question of LinkedList.


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.


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;


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.