Given a linked list, swap every two adjacent nodes and return its head.
Example
I: 1->2->3->4
O: 2->1->4->3
Analysis
Give a dummy head and write a swap next 2 helper.
Code
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
while (current != null) {
current = swapNextPair(current);
}
return dummy.next;
}
// swap pair then return the start of next pair
// base -> a -> b -> c
private ListNode swapNextPair(ListNode base) {
if (base.next == null || base.next.next == null) {
return null; // no more pairs to swap
}
// swap
ListNode a = base.next;
ListNode b = base.next.next;
ListNode c = base.next.next.next;
base.next = b;
b.next = a;
a.next = c;
return a;
}
Given a linked list, reverse the list in a group of k nodes.
Assume k is a valid number. If the length of the leftover nodes is less than k, do nothing.
Example
I: 1->2->3->4->5
k = 2, O: 2->1->4->3->5
k = 3, O: 3->2->1->4->5
Approach
Step 1 Check the current group length >= k
Step 2 Reverse n_1 to n_k
Step 3 Set base.next to n_k and n_1.next to n_k+1
Code
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode current = dummy;
while (current != null) {
current = reverseNextGroup(current, k);
}
return dummy.next;
}
// base -> n_1 -> ... -> n_k -->n_k+1
private ListNode reverseNextGroup(ListNode base, int k) {
ListNode travel = base.next;
for (int i = 0; i < k; i++) {
if (travel == null) return null;
travel = travel.next;
}
// reverse
ListNode current = base.next.next;
ListNode prev = base.next;
ListNode temp;
while (k > 1 && current != null) {
temp = current.next;
current.next = prev;
prev = current;
current = temp;
k--;
}
// connect
ListNode newBase = base.next;
base.next.next = current;
base.next = prev;
// return new base
return newBase;
}
