[LeetCode] 2095. Delete the Middle Node of a Linked List (C#)

https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list

 

linkedlist의 head가 주어진다.

해당 linkedlist의 middle 노드를 삭제하고, 변경된 리스트의 head를 반환하는 문제.

middle 노드의 기준은 리스트의 사이즈를 n이라고 가정하고 [ n / 2 ] 번째 노드를 뜻한다.

 

 

1. 원 포인터를 사용한 풀이

• middle 노드가 몇 번째인지 확인하는 과정이 들어간다.
• middle 노드 직전에서 순회를 멈추고 다다음 노드를 Next 로 바라본다.
• 원소가 1개인 경우는 예외 케이스로 처리

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

public class Solution
{
    public ListNode DeleteMiddle(ListNode head)
    {
        if (head.next == null)
        {
            return null;
        }
        
        var current = head;
        var listLength = 0;
        while (current != null)
        {
            listLength++;
            current = current.next;
        }

        var togo = listLength / 2;
        current = head;
        while (togo-- != 1)
        {
            current = current.next;
        }
        
        current.next = current.next.next;
        
        return head;
    }
}

 

 

 

2. 투포인터를 사용한 풀이

• 하나씩 이동하는 slow 포인터와 2칸씩 이동하는 fast 포인터를 함께 사용한다.
• fast 포인터가 더 이상 움직이지 못하는 시점이 slow 포인터의 middle 직전 노드가 된다.

public class Solution
{
    public ListNode DeleteMiddle(ListNode head)
    {
        var slowPrev = new ListNode(-1);
        slowPrev.next = head;
        
        var slow = slowPrev;
        var fast = head;

        while (fast?.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }

        slow.next = slow.next.next;

        return slowPrev.next;
    }
}