Reverse Linked List II

Problem Description

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.

Intuition

We split three part by this linked list, head, body and tail.

As Problem Description, we need to reverse body. And Combine head, body and tail.

Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
	ListNode* reverseBetween(ListNode* head, int left, int right) {
		int count = 1;
		
		ListNode* dummy = new ListNode(0, head); // we need to create a dummy Node to avoid the left = 1
		ListNode* prev = dummy;
		
		while(count < left){
			prev = prev->next;
			count++;
		}
		
		ListNode* start = prev->next;
		ListNode* end = start;
		
		while(count < right){
			end = end->next;
			count++;
		}
		
		ListNode* tail = end->next;
		end->next = nullptr;
		
		ListNode* newHead = ReverseLinkedList(start);
		
		prev->next = newHead;
		start->next = tail;
		
		return dummy->next;
	}

  

	ListNode* ReverseLinkedList(ListNode* head){
		
		ListNode* prev = nullptr;
		ListNode* curr = head;
		
		while(curr != nullptr) {
			ListNode* temp = curr->next;
			curr->next = prev;
			prev = curr;
			curr = temp;
		}
		
		return prev;
	}
};