Problem

Given a singly linked list and a number k, write an algorithm to reverse every alternate k nodes in the linked list. If there are fewer than k nodes left at the end, leave them as is.

Examples

Example 1:

---
title: Input
---

 graph LR
   A1[1] --> B2[2] --> C3[3] --> D4[4] --> E5[5] --> F6[6] --> G7[7] --> H8[8]
 
   classDef swapped fill:#ffcc00,stroke:#000,stroke-width:2px;
  
---
title: Output
---

 graph LR
   C3[3]:::swapped --> B2[2]:::swapped --> A1[1]:::swapped --> D4[4] --> E5[5] --> F6[6] --> H8[8]:::swapped --> G7[7]:::swapped
 
   classDef swapped fill:#ffcc00,stroke:#000,stroke-width:2px;
  
1
2

Input: head = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null, k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 8 -> 7 -> null

Example 2:

---
title: Input
---

 graph LR
   A1[1] --> B2[2] --> C3[3] --> D4[4] --> E5[5]
 
   classDef swapped fill:#ffcc00,stroke:#000,stroke-width:2px;
  
---
title: Output
---

graph LR
	B2[2]:::swapped --> A1[1]:::swapped --> C3[3] --> D4[4] --> E5[5]
	
	classDef swapped fill:#ffcc00,stroke:#000,stroke-width:2px;
  
1
2

Input: head = 1 -> 2 -> 3 -> 4 -> 5 -> null, k = 2
Output: 2 -> 1 -> 3 -> 4 -> 5 -> null

Solution

Method 1 - Iteration

  1. Initialization:
    • Use a pointer to traverse the list and reverse the nodes.
    • Use an additional pointer to manage connections between reversed and non-reversed segments.
  2. Reverse Alternate k Nodes:
    • Reverse the first k nodes.
    • Skip the next k nodes.
    • Repeat the above steps until reaching the end of the list.
  3. Edge Cases:
    • If there are fewer than k nodes left at the end, do not reverse them.

Code

 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

public class Solution {
    public ListNode reverseAlternateKNodes(ListNode head, int k) {
        if (head == null || k <= 0)
            return head;

        ListNode current = head;
        ListNode prevTail = null; // Last node of the previous segment
        ListNode newHead = null;
        boolean shouldReverse = true;

        while (current != null) {
            ListNode segmentHead = current;
            ListNode prev = null;
            int count = 0;

            // Traverse k nodes
            while (current != null && count < k) {
                ListNode nextNode = current.next;
                if (shouldReverse) {
                    current.next = prev;
                }
                prev = current;
                current = nextNode;
                count++;
            }

            if (shouldReverse) {
                if (newHead == null) {
                    newHead = prev;
                }
                if (prevTail != null) {
                    prevTail.next = prev;
                }
                prevTail = segmentHead;
            } else {
                if (prevTail != null) {
                    prevTail.next = segmentHead;
                }
                prevTail = segmentHead;
            }

            shouldReverse = !shouldReverse; // Toggle the shouldReverse flag
        }

        return newHead;
    }
}
 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

class Solution:
    def reverseAlternateKNodes(self, head: ListNode, k: int) -> ListNode:
        if not head or k <= 0:
            return head

        current = head
        prev_tail = None  # Last node of the previous segment
        new_head = None
        should_reverse = True

        while current:
            segment_head = current
            prev = None
            count = 0

            # Traverse k nodes
            while current and count < k:
                next_node = current.next
                if should_reverse:
                    current.next = prev
                prev = current
                current = next_node
                count += 1

            if should_reverse:
                if new_head is None:
                    new_head = prev
                if prev_tail:
                    prev_tail.next = prev
                prev_tail = segment_head
            else:
                if prev_tail:
                    prev_tail.next = segment_head
                prev_tail = segment_head

            should_reverse = (
                not should_reverse
            )  # Toggle the should_reverse flag

        return new_head

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. Each node is processed at most twice.
  • 🧺 Space complexity: O(1), as we only use a constant amount of extra space for pointers.