Swap Nth Node with Head (Easy)

설명

Singly Linked List의 head와 정수 "N"이 인수로 전달됩니다.
head와 head에서 N번째 노드로 교환합니다. 반환값은 새로운 Linked list의 head입니다.

예

N = 4의 예를 살펴 보겠습니다.

head를 첫 번째로 네 번째 노드의 28과 head의 7을 교환하므로 다음과 같습니다.

Solution

Runtime Complexity O(n)

Linked List 에 대해서 주사할 필요가 있으므로 최악 O(n) 걸립니다.

Space Complexity O(1)

복수의 포인터만을 사용하므로, 메모리 효율은 O(1)가 됩니다.

Step By Step

두 개의 포인터를 준비합니다.

현재 포인터가 N 번째 노드를 가리킬 때까지 반복합니다.

현재 포인터가 네 번째 노드를 가리키므로 여기서 루프를 멈 춥니 다.

여기에서 노드를 교환합니다.




여기서 Swapping 할 수 있었으므로, current의 포인터를 돌려줍니다.

구현

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

감상

Linked List에 Swapping, Sorting 등의 간단한 조작을 적용하려면
여러 포인터를 활용하여 해결책을 볼 수 있다고 생각합니다.