Linked List Reverse¶
Table of Contents¶
- 206. Reverse Linked List (Easy)
- 92. Reverse Linked List II (Medium)
- 24. Swap Nodes in Pairs (Medium)
- 25. Reverse Nodes in k-Group (Hard)
- 2074. Reverse Nodes in Even Length Groups (Medium)
206. Reverse Linked List¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def reverse_list_iterative(head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
return prev
def reverse_list_recursive(head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(cur, prev):
if not cur:
return prev
temp = cur.next
cur.next = prev
return reverse(temp, cur)
return reverse(head, None)
def test_reverse_list():
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_iterative(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
ll = LinkedList([1, 2, 3, 4, 5])
ll.head = reverse_list_recursive(ll.head)
assert ll.to_array() == [5, 4, 3, 2, 1]
92. Reverse Linked List II¶
"""
- Reverse a linked list from position left to position right. Return the linked list after reversing.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def reverseBetween(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(next=head)
p0 = dummy
for _ in range(left - 1):
if p0.next is None:
break
p0 = p0.next
pre = None
cur = p0.next
for _ in range(right - left + 1):
if not cur:
break
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
if p0.next:
p0.next.next = cur
p0.next = pre
return dummy.next
def test_reverse_between():
head = list_from_array([1, 2, 3, 4, 5])
left = 2
right = 4
result = reverseBetween(head, left, right)
assert list_to_array(result) == [1, 4, 3, 2, 5]
head = list_from_array([5])
left = 1
right = 1
result = reverseBetween(head, left, right)
assert list_to_array(result) == [5]
head = list_from_array([3, 5])
left = 1
right = 2
result = reverseBetween(head, left, right)
assert list_to_array(result) == [5, 3]
#include <cassert>
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head || left == right) return head;
ListNode dummy(0);
dummy.next = head;
ListNode* p0 = &dummy;
for (int i = 0; i < left - 1; ++i) {
p0 = p0->next;
}
ListNode* pre = nullptr;
ListNode* cur = p0->next;
int count = right - left + 1;
while (count--) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
p0->next->next = cur;
p0->next = pre;
return dummy.next;
}
};
int main() {
Solution solution;
ListNode* head1 = new ListNode(
1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
int left1 = 2, right1 = 4;
ListNode* result1 = solution.reverseBetween(head1, left1, right1);
ListNode* expected1 = new ListNode(
1, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(5)))));
for (ListNode *p = result1, *q = expected1; p != nullptr && q != nullptr;
p = p->next, q = q->next) {
assert(p->val == q->val);
}
ListNode* head2 = new ListNode(5);
int left2 = 1, right2 = 1;
ListNode* result2 = solution.reverseBetween(head2, left2, right2);
ListNode* expected2 = new ListNode(5);
for (ListNode *p = result2, *q = expected2; p != nullptr && q != nullptr;
p = p->next, q = q->next) {
assert(p->val == q->val);
}
return 0;
}
24. Swap Nodes in Pairs¶
"""
- Given a linked list, swap every two adjacent nodes and return its head.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def swap_pairs(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
n0 = dummy
n1 = dummy.next
while n1 and n1.next:
n2 = n1.next
n3 = n2.next
n0.next = n2
n2.next = n1
n1.next = n3
n0 = n1
n1 = n3
return dummy.next
def test_swap_pairs():
head = list_from_array([1, 2, 3, 4, 5])
assert list_to_array(swap_pairs(head)) == [2, 1, 4, 3, 5]
25. Reverse Nodes in k-Group¶
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def reverse_k_group(head: Optional[ListNode], k: int) -> Optional[ListNode]:
n = 0
cur = head
while cur:
n += 1
cur = cur.next
p0 = dummy = ListNode(next=head)
pre = None
cur = head
while n >= k:
n -= k
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
nxt = p0.next
nxt.next = cur
p0.next = pre
p0 = nxt
return dummy.next
def test_reverse_k_group():
head = list_from_array([1, 2, 3, 4, 5])
assert list_to_array(reverse_k_group(head, 2)) == [2, 1, 4, 3, 5]