Problem

Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched. Input: A linked list, A number k.

Examples

Example 1:

---
title: Input List with k = 4
---
 graph LR
   A1[1] --> B2[2] --> C3[3] --> D4[4]:::kth_node --> E5[5] --> F6[6] --> G7[7] --> H8[8]:::kth_node --> I9[9] --> J10[10]
   classDef kth_node fill:#FFA500,stroke:#000,stroke-width:2px;
  
---
title: Output List
---
  graph LR
   A4[4] --> B2[2] --> C3[3] --> D1[1] --> E8[8] --> F6[6] --> G7[7] --> H5[5] --> I9[9] --> J10[10]
  
1
2

Input : head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 4
Output: [4, 2, 3, 1, 8, 6, 7, 5, 9, 10]

Solution

Method 1 - Iteration

Here is the plan:

  1. Identify the Nodes to be Swapped in Each k-Segment:
    • Traverse the list in chunks of k nodes.
    • For each chunk, swap the 1st and k-th node.
  2. Skip Remaining Steps if There Are Fewer Than k Nodes Left.

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

class Solution {
    public ListNode swapEveryKthNode(ListNode head, int k) {
        // Edge case: If k <= 1 or the list is empty, no need to swap
        if (k <= 1 || head == null) {
            return head;
        }

        // Dummy node to handle the edge cases easily
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode current = head;
        ListNode prev = dummy;

        while (true) {
            ListNode start = current;
            ListNode end = current;
            ListNode prevEnd =
                current; // will be used to connect to the next part

            // Check if there are at least k nodes left
            int count = 0;
            while (count < k && current != null) {
                prevEnd = current;
                current = current.next;
                count++;
            }

            if (count < k) {
                break; // If fewer than k nodes left, exit the loop
            }

            // Perform the swap within this k-segment
            // Save prev pointers to 1st and last nodes in the segment
            ListNode firstNodePrev = prev;
            ListNode firstNode = start;
            ListNode kNodePrev = prevEnd;
            ListNode kNode = prevEnd;

            // Swap the first and k-th nodes
            firstNodePrev.next = kNode;
            kNodePrev.next = firstNode;
            ListNode temp = firstNode.next;
            firstNode.next = kNode.next;
            kNode.next = temp;

            // Move prev pointer to the last node after the swap
            prev = firstNode;
        }

        return dummy.next;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        ListNode head = solution.createLinkedList(arr);

        int k = 4; // swapping every 4th node

        System.out.println("Original list:");
        solution.printLinkedList(head);

        ListNode newHead = solution.swapEveryKthNode(head, k);

        System.out.println("After swapping every 4th node:");
        solution.printLinkedList(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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

def swapEveryKthNode(head: ListNode, k: int) -> ListNode:
    # Edge case: If k <= 1 or the list is empty, no need to swap
    if k <= 1 or head is None:
        return head

    # Dummy node to handle the edge cases easily
    dummy = ListNode(0)
    dummy.next = head
    current = head
    prev = dummy

    while True:
        start = current
        end = current
        prevEnd = current

        # Check if there are at least k nodes left
        count = 0
        while count < k and current is not None:
            prevEnd = current
            current = current.next
            count += 1

        if count < k:
            break  # If fewer than k nodes left, exit the loop

        # Perform the swap within this k-segment
        # Save prev pointers to 1st and last nodes in the segment
        firstNodePrev = prev
        firstNode = start
        kNodePrev = prevEnd
        kNode = prevEnd

        # Swap the first and k-th nodes
        firstNodePrev.next = kNode
        kNodePrev.next = firstNode
        temp = firstNode.next
        firstNode.next = kNode.next
        kNode.next = temp

        # Move prev pointer to the last node after the swap
        prev = firstNode

    return dummy.next


# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 4
head = create_linked_list(arr)
print("Original List:")
print_linked_list(head)

new_head = swapEveryKthNode(head, k)
print("After Swapping Every 4th Node:")
print_linked_list(new_head)

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. Each node is visited a constant number of times.
  • 🧺 Space complexity: O(1), as the solution uses a constant amount of extra space.