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. Screen Shot 2020-01-10 at 16.35.08.png Since head is the first and 28 of the fourth node and 7 of the head are exchanged, it becomes as follows. Screen Shot 2020-01-10 at 16.35.25.png

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. Screen Shot 2020-01-10 at 16.42.22.png Loop until the current pointer points to the Nth node. Screen Shot 2020-01-10 at 16.43.15.png The current pointer points to the 4th node, so stop the loop here. Screen Shot 2020-01-10 at 16.45.12.png From here, we will exchange nodes. Screen Shot 2020-01-10 at 16.46.28.png Screen Shot 2020-01-10 at 16.47.12.png Screen Shot 2020-01-10 at 16.47.32.png Screen Shot 2020-01-10 at 16.47.50.png 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.

Recommended Posts

Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm