[알고리즘] linked list 문제

206. Reverse Linked List

linked list 뒤집는 방법

방법1)

• head의 다음 노드부터 시작해서 node를 차례로 iterate할 것이다.
• iterate하면서 만나는 node들의 pointer를 반대 방향으로 바꿔나간다.
  

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        cur = head
        
        while cur is not None:
            nextNode = cur.next
            cur.next = prev
            
            prev = cur
            cur = nextNode
            
        return prev

방법2) recursive 재귀

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        reversedSublist = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return reversedSublist

방법3) 기존 head노드를 점점 뒤로 옮기면서 currentHead 갱신하는 방법

아래는 C++ template

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) {
            return head;
        }
        ListNode* currentHead = head;
        while (head->next) {
            ListNode* p = head->next;
            head->next = p->next;
            p->next = currentHead;
            currentHead = p;
        }
        return currentHead;
    }
};

203. Remove Linked List Elements

처음쓴 코드)

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        
        prev = None
        cur = head
        
        while cur:
            if cur.val == val:
                if prev is None:
                    head = cur.next
                    prev = None
                else:
                    prev.next = cur.next
            else:
                prev = cur
                
            cur = cur.next
            
        return head

정리) sentinel node를 사용해보자.

일반적인 linked list 노드의 deletion은 prevode.next = curnode.next 라는 논리로 쉽게 해결이 된다.

• 하지만 여기서는 dummy head를 사용하고 있지 않으므로 삭제하려는 노드가 head node인 경우에 예외적으로 처리야하는 경우가 생긴다.
• 그래서 나도 처음 코드를 작성할때 prev가 None인 경우는 삭제할 노드가 head노드 이므로 if문으로 따로 분기하여 처리하였다.

다음에 설명할 내용에서는 sentinel node를 pseudo-head로 사용해서 모든 case를 standard하게 처리하고자 한다.

• sentinel node는 tree나 linked list에서 psudo-head나 pseudo-tail, marker of level 등과 같은 용도로 사용된다.
• 문제상황을 standardize하는 용도로 주로 쓰이기 때문에 data를 holding하지는 않는다.

sentinel 사용 코드)

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        sentinel = ListNode(0)
        sentinel.next = head
        
        prev = sentinel
        cur = head
        
        while cur:
            if cur.val == val:
                prev.next = cur.next
            else:
                prev = cur
            cur = cur.next
        
        return sentinel.next

sentinel 활용 추가문제

• 146. LRU Cache
• 1161. Maximum Level Sum of a Binary Tree

328. Odd Even Linked List

처음풀었을때는 linked list내의 cycle로 인해 실패했다. cycle은 짝수번째 노드의 끝이 null로 끝나지 않아서 생긴 문제였다.

풀이를 보니 odd node를 기준으로 뒤에 even과 even.next(즉, odd의 next가 될 노드)만 존재하지는에 따라 while문을 돌려주면 내가 생각한 조건보다도 훨씬 간단해졌다.
내가 복잡하게 생각한 이유는 null의 next를 접근하려는 오류를 막으려고 그런것인데 odd를 기준으로 even과 even.next가 있다면 even.next.next 접근이 에러가 나지 않을 것이므로 간단해진다.

또한 1->2->3->4->5->null, 1->2->3->4->null 이므로 odd를 기준으로 while문을 작성한다면
전자의 경우는 odd가 3일때, 4는 even.next.next가 null이라서 4->null이 되고,
후자의 경우는 애초에 4->null이므로 odd가 3일때 even->next가 null이라서 while문이 돌아가지 않더라도 내가 범했던 문제(짝수번째 노드 끝이 null로 끝나지 않아서 cycle이 생김)를 해결하게 된다.

그래서 정답은 아래와 같다.

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        
        odd = head
        even = head.next
        even_head = head.next
        
        while even and even.next:
            odd.next = odd.next.next
            odd = odd.next
            even.next = even.next.next
            even = even.next
            
        odd.next = even_head
        
        return head

234. Palindrome Linked List

아이디어는 linked list의 절반지점을 slow와 fast runner방식으로 찾은 뒤, 절반의 뒤쪽에 해당하는 list를 뒤집어서 앞의 list 절반과 비교하는 것이다.

처음 푼 코드)

class Solution:
    def flip(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head
        
        currHead = head
        
        while head.next:
            p = head.next
            head.next = p.next
            p.next = currHead
            currHead = p
        
        return currHead
    
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        sentinel = ListNode(0)
        sentinel.next = head
        
        slow = sentinel
        fast = sentinel
        
        if head.next is None:
            return True
        
        #리스트 절반지점 찾기
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        #절반 뒤쪽 list 뒤집기
        reversedList = self.flip(slow.next)
        
        #그냥 깔끔함을 위해 linked list 2개 분리시킴.
        #아래 줄은 없어도 되긴함. slow.next접근할 일이 없어서.
        slow.next = None
        
        
        while reversedList:
            if reversedList.val == head.val:
                reversedList = reversedList.next
                head = head.next
            else: 
                return False
        return True