링크드리스트 문제를 해결할 때 가장 먼저 기억해야 할 점은 가상의 헤드 노드를 설정하는 것입니다.

LeetCode 24: 두 노드씩 교환하기 주어진 링크드리스트에서 두 개의 노드씩 교환하는 문제입니다. 이때 중요한 것은 적절한 위치의 노드를 참조하는 것입니다. 특히 두 개의 노드를 교환하기 전의 노드를 기억해야 합니다.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (prev.next != null && prev.next.next != null) {
            ListNode first = prev.next;
            ListNode second = first.next;
            ListNode temp = second.next;
            
            prev.next = second;
            second.next = first;
            first.next = temp;
            
            prev = first;
        }
        return dummy.next;
    }
}

LeetCode 19: 링크드리스트에서 뒤에서 N번째 노드 제거하기 링크드리스트에서 뒤에서 N번째 노드를 제거하는 문제입니다. 이 문제는 두 개의 포인터를 사용하여 해결할 수 있습니다. 먼저 빠른 포인터를 N번 이동한 후, 느린 포인터와 함께 이동시킵니다. 빠른 포인터가 마지막 노드에 도달하면, 느린 포인터는 제거해야 하는 노드 바로 앞에 위치하게 됩니다.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

LeetCode 인터뷰 문제 0207: 두 링크드리스트가 교차하는 지점 찾기 두 링크드리스트가 교차하는 지점을 찾아내는 문제입니다. 이 문제는 두 가지 방법으로 해결할 수 있습니다. 첫 번째 방법은 각 링크드리스트의 길이를 구하고, 더 긴 리스트의 포인터를 먼저 이동시키는 것입니다. 두 번째 방법은 두 포인터가 각 리스트를 순회하면서 교차 지점을 찾는 것입니다.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pointerA = headA, pointerB = headB;
        while (pointerA != pointerB) {
            pointerA = pointerA == null ? headB : pointerA.next;
            pointerB = pointerB == null ? headA : pointerB.next;
        }
        return pointerA;
    }
}

LeetCode 142: 순환 링크드리스트의 시작 지점 찾기 순환 링크드리스트가 존재할 경우 그 시작 지점을 찾아내는 문제입니다. 이 문제는 먼저 순환이 있는지 확인한 후, 순환의 시작 지점을 찾습니다. 순환이 있을 경우, 한 포인터는 시작 지점에서 다른 포인터는 교차 지점에서 출발하여 두 포인터가 만나는 지점이 순환의 시작 지점임을 이용합니다.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        boolean hasCycle = false;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        if (!hasCycle) return null;
        
        ListNode ptr1 = head;
        ListNode ptr2 = slow;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }
}