[JAVA] Algorithm gymnastics 14

Swap Nth Node with Head (Easy)

Description

The head of the Singly Linked List and the integer "N" are passed as arguments. Swap the head and the Nth node from the head. The return value is the head of the new Linked list.

Example

Let's look at an example with N = 4. Since head is the first and 28 of the fourth node and 7 of the head are exchanged, it becomes as follows.

Solution Runtime Complexity O(n) It takes O (n) at worst because it needs to scan against the Linked List. Space Complexity O(1) Since only multiple pointers are used, the memory efficiency is O (1).

Step By Step Prepare two pointers. Loop until the current pointer points to the Nth node. The current pointer points to the 4th node, so stop the loop here. From here, we will exchange nodes. Now that we've swapped, we'll return a pointer to current.

Implementation

SwapNth.java

class SwapNth{
  // Node indices starts from 1.
  public LinkedListNode SwapNthNode(LinkedListNode head, int n) {

    if (head == null || n < 1) return head; // Edge case

    LinkedListNode cur = head;
    LinkedListNode prev = null;

    int count = 1;

    while (count < n && cur != null) {
      prev = cur;
      cur = cur.next;
      count++;
    }

    if (cur == null) return head;

    // Swapping
    prev.next = head;
    LinkedListNode temp = head.next;
    head.next = cur.next;
    cur.next = temp;
    
    return cur;
  }
} 

Impressions

If you want to apply simple operations such as Swapping and Sorting to the Linked List I think you can find a solution by using multiple pointers.