[LeetCode] 19. Remove Nth Node From End of List - 문제풀이

Description

주어진 LinkedList에서 끝에서 n번째 리스트노드를 제거하여 반환하는 문제입니다.

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

ListNode:

public class ListNode {
    public int val;
    public ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Solution 1. Pointer 두개의 갭을 이용

public ListNode removeNthFromEnd(ListNode head, int n) {

    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode slow = dummyHead;
    ListNode fast = dummyHead;

    while(n>0){ //n만큼 두 포인터를 벌려줌
        fast = fast.next;
        n--;
    }
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }
    slow.next = slow.next.next;
    return dummyHead.next;
}

slow, fast 두개의 포인터를 두고 포인터간의 갭을 n만큼 벌립니다. 이후 fast포인터가 맨 마지막 노드에 올때까지 slow포인터와 같이 이동시켜주면 slow포인터는 마지막노드에서 n만큼 못간 우리가 원하는 위치에 위치하게 됩니다. 공간복잡도O(1) 시간복잡도O(N)의 Onepass 솔루션.

Solution 2. length 체크 + 배열이용

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode[] a = new ListNode[30];
    int len = 0;
    ListNode node = head;
    while(node!=null){ // i= index+1 (length)
        a[len++] = node;
        node=node.next;
    }

    if(len == 1){  // 리스트 길이가 1개인 경우 무조건 제거
        head = null;
    } else if(len-n == 0){ //  제거노드가 맨 앞이 되는 케이스
        head = head.next;
    } else{
        node =  a[len-n-1];  //제거 대상 이전 노드
        node.next = node.next.next;
    }
    return head;
}

LinkedList의 길이를 체크하면서 순회할때 각각의 인덱스에 맞게 노드들을 배열에 넣어주고 length-n 위치에 있는 노드를 제거해줍니다. 엣지케이스만 신경쓰면 이해하기 쉬운코드며 시간복잡도, 공간복잡도는 O(N).