[LeetCode 75/Linked List] 2095 - Delete the Middle Node of a Linked List / 328 - Odd Even Linked List / 206 - Reverse Linked List / 2130 - Maximum Twin Sum of a Linked List (Java)

2095 - Delete the Middle Node of a Linked List

---

풀이

길이 n인 리스트에서 인덱스 ⌊n/2⌋ (0-based) 노드 삭제

ex. [1, 3, 4, 7, 1, 2, 6] -> n = 7, ⌊7/2⌋ = 3 => 7 삭제

 

`head.next == null`: 노드 1개 == middle -> 삭제 => null

 

리스트 길이 모름 -> `fast`: 2칸씩 이동 / `slow`: 1칸씩 이동

`fast`가 끝에 도달하면 `slow`는 middle에 있음

(`prev`: `slow`의 이전 노드 저장)

ListNode slow = head;
ListNode fast = head;
ListNode prev = null;

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

prev.next = slow.next;

---

코드

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = null;

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

        prev.next = slow.next;

        return head;
    }
}

---

328 - Odd Even Linked List

---

풀이

인덱스 기준으로 홀수 노드 먼저, 그 다음 짝수 노드들

 

`odd`: 홀수 체인 포인터 / `even`: 짝수 체인 포인터

(`evenHead`: 짝수 시작점 저장)

ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;

while (even != null && even.next != null) {
    odd.next = even.next;
    odd = odd.next;

    even.next = odd.next;
    even = even.next;
}

odd.next = evenHead;

---

코드

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;

        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;

            even.next = odd.next;
            even = even.next;
        }

        odd.next = evenHead;

        return head;
    }
}

---

206 - Reverse Linked List

---

풀이

포인터 방향 뒤집기

-> 현재 노드 방향 뒤집고 앞으로 한 칸 이동

=> `prev`: 이전 노드 / `cur`: 현재 노드 / `next`: 다음 노드

---

코드

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;         
            prev = cur;              
            cur = next;              
        }

        return prev; 
    }
}

---

2130 - Maximum Twin Sum of a Linked List

---

풀이

양쪽 끝끼리 짝 만들어서 가장 큰 합 구하기

=> i번째 노드 <-> (n - 1 - i)번째 노드

ex. [5, 3, 2, 1] -> (0 <-> 3) -> 5 + 1 = 6 / (1 <-> 2) -> 4 + 2 = 6 => max = 6

 

중간 찾기

`fast`: 2칸씩 이동 / `slow`: 1칸씩 이동

`fast`가 끝에 도달하면 `slow`는 middle에 있음

ListNode slow = head;
ListNode fast = head;

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

5 → 4 → 2 → 1
        ↑
      slow

 

뒤 절반 reverse

`slow`: 뒤 절반 시작점 -> `ListNode cur = slow`

ListNode prev = null;
ListNode cur = slow;

while (cur != null) {
    ListNode next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

5 → 4     1 → 2
           ↑
         prev

 

twin sum 계산

`prev`: 뒤집한 리스트의 시작점 -> `ListNode second = prev`

int max = 0;
ListNode first = head;
ListNode second = prev;

while (second != null) {
    max = Math.max(max, first.val + second.val);
    first = first.next;
    second = second.next;
}

first  = head  → 5 → 4
second = prev  → 1 → 2

---

코드

class Solution {
    public int pairSum(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

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

        ListNode prev = null;
        ListNode cur = slow;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        int max = 0;
        ListNode first = head;
        ListNode second = prev;

        while (second != null) {
            max = Math.max(max, first.val + second.val);
            first = first.next;
            second = second.next;
        }

        return max;
    }
}

---

출처

LeetCode 75 - Study Plan - LeetCode