The link to the problem: https://leetcode.com/problems/reverse-linked-list-ii/
This problem requires us to reverse a linked list node from position m to n. Do it in one pass.
Note that 1 ≤ m ≤ n ≤ length of the list
For example, 1->2->3->4->5 , m = 2, n = 4
The output should be 1->4->3->2->5
Thoughts:
To be honest, I’m not good at these types of problems.
To know how to solve this problem, it is recommended to know how to solve 206. Reverse Linked List.
I was trying to add some idea of how to solve the problem but it is hard for me to explain clearly in a few sentences. Hence, I wrote an extra story about it.
👉 Please check out Leetcode — 206. Reverse Linked List (recursive version) to know better about the idea of reversing the list!
After reading it, we now know how to reverse a linked list. Now this problem doesn’t seem too scary, is it? 😅
Program Logic:
This problem has three inputs, head, m, and n.
It is important to have a dummy node that points to our “head of the result” since it is not guaranteed that head is the “head of the result”. (only if m is not 1).
The idea is to divide the linked list into 3 parts:
a. dummy -> head -> … -> the node before m
b. node m -> …. -> node n
(will be reversed, so later will be node n ->…-> node m)
c. the node right after n -> …. -> null
Hence, the step of the code will be:
1. keep traversing the linked list till we reach node m
2. reverse part b of the linked list
3. bond the tail of part a with the head of part b (i.e., node n)
4. bond the tail of part b (i.e., node m) with the head of part c.
Below is the 0ms code beats 100%:
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head==null||head.next==null)
return head; //step 1.
int count = 1;
ListNode dummy = new ListNode(0,head);
ListNode prev = dummy;
while(count<m)
{
prev = head;
head = head.next;
count++;
} //step 2.
ListNode a_tail = prev; //tail of part a
ListNode b_tail = head; //"tail of part b"
prev = null; //later will be the head of b
ListNode cur = head; //later will be head of part c
int total = n-m+1; //length of reverse list
for(int i=0;i<total;i++)
{
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
//step 3. connect tail of a and head of b
a_tail.next = prev; //step 4. connect tail of b and head of c
b_tail.next = cur;
return dummy.next;
}
Time complexity is O(n) since we just run the whole linked list.
Space complexity is O(1). ✌️
