Reverse Linked List II Problem: 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.
Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]
Table of Contents
Reverse Linked List II Problem Solution
Problem Solution In Python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
counts = 0
stack = []
dummy = ListNode(0)
pre = dummy
while head:
counts += 1
if counts < m:
pre.next = head
pre = pre.next
elif counts >=m and counts <=n:
stack.append(head)
else:
break
head = head.next
while stack:
pre.next = stack.pop()
pre = pre.next
pre.next = head
return dummy.next
Problem Solution In Java
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode preRev = null;
ListNode curr = head;
int i = 1;
while(i<m) { preRev = curr; curr = curr.next; i++; }
ListNode end = curr;
ListNode pre = null;
while(i<=n) {
ListNode temp = curr.next;
curr.next = pre;
pre = curr;
curr = temp;
i++;
}
end.next = curr;
if(preRev != null) preRev.next = pre;
return preRev == null ? pre: head;
}
Problem Solution In C++
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(!head->next || m == n) return head;
ListNode* l = head;
for(int i = 0; i < m-2; i++) l = l->next;
ListNode* pre = NULL;
ListNode* cur = m == 1 ? l : l->next;
ListNode* next = cur->next;
ListNode* reverseHead = cur;
for(int i = 0; i < n-m+1; i++){
cur->next = pre;
pre = cur;
cur = next;
next = next ? next->next : NULL;
}
reverseHead->next = cur;
if(m != 1) l->next = pre;
return m == 1 ? pre : head;
}
Problem Solution In C
struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
if(!head->next) return head;
if(m == n)return head;
if(!head->next->next){
struct ListNode* tmp = head->next;
head->next->next = head;
head->next = NULL;
return tmp;
}
struct ListNode* revtail;
struct ListNode* orghead;
struct ListNode* scanner = head;
struct ListNode* before = NULL;
int counter = 0;
while(counter++ < m - 1){
before = scanner;
scanner = scanner->next;
}
orghead = before;
before = scanner;
struct ListNode* curr = scanner->next;
struct ListNode* curr_next = NULL;
revtail = scanner;
counter = 0;
while(counter++<(n - m)){
curr_next = curr->next;
curr->next = before;
before = curr;
curr = curr_next;
}
if(orghead)
orghead->next = before;
revtail->next = curr;
return orghead == NULL ? before : head;
}