[LEET CODE] 234. Palindrome Linked List ( 연결리스트, 런너 기법)

# Problem

Given the head of a singly linked list, return true if it is a palindrome. Constraints: The number of nodes in the list is in the range [1, 105]. 0 <= Node.val <= 9

 

# My Answer

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        h=[]
        while head:
            h.append(head.val)
            head = head.next
        if h==h[::-1]:
            return True

 

# Solution 1 - 리스트 변환

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        q: List = []

        if not head:
            return True

        node = head
        # 리스트 변환
        while node is not None:
            q.append(node.val)
            node = node.next

        # 팰린드롬 판별
        # 시작과 끝 하나씩 비교
        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False

        return True

 

# Solution 2 - 데크를 이용한 최적화

import collections
from typing import Deque


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        # 데크 자료형 선언
        q: Deque = collections.deque()

        if not head:
            return True

        node = head
        while node is not None:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.popleft() != q.pop():
                return False

        return True

파이썬의 리스트에서 pop(0)을 하게 되면 모든 값이 한 칸씩 shifting 되며 , 시간 복잡도 O(n) 발생

파이썬의 데크(Deque)는 이중 연결 리스트로 양쪽 방향 모두 추출하는데 시간 복잡도 O(1)에 실행 

     -> popleft(), pop() 사용

 

실행시간이 # Solution 1 보다 2배 이상 빨라짐

 

# Solution 3 - 고(GO)를 이용한 데크 구현

성능이 매우 좋지만 Go는 데크 자료형을 지원하지 않기 때문에 직접 구현해야함 - 비효율적

// Go
// 데크(deque) 자료형을 Go로 바닥부터 구현한 풀이
const minCapacity = 16

type Deque struct {
    buf    []interface{}
    head   int
    tail   int
    count  int
    minCap int
}

func (q *Deque) Len() int {
    return q.count
}

func (q *Deque) PushBack(elem interface{}) {
    q.growIfFull()

    q.buf[q.tail] = elem
    q.tail = q.next(q.tail)
    q.count++
}

func (q *Deque) PopFront() interface{} {
    if q.count <= 0 {
        panic("deque: PopFront() called on empty queue")
    }
    ret := q.buf[q.head]
    q.buf[q.head] = nil
    q.head = q.next(q.head)
    q.count--

    return ret
}

func (q *Deque) PopBack() interface{} {
    if q.count <= 0 {
        panic("deque: PopBack() called on empty queue")
    }

    q.tail = q.prev(q.tail)

    ret := q.buf[q.tail]
    q.buf[q.tail] = nil
    q.count--

    return ret
}

func (q *Deque) prev(i int) int {
    return (i - 1) & (len(q.buf) - 1)
}

func (q *Deque) next(i int) int {
    return (i + 1) & (len(q.buf) - 1)
}

func (q *Deque) growIfFull() {
    if len(q.buf) == 0 {
        if q.minCap == 0 {
            q.minCap = minCapacity
        }
        q.buf = make([]interface{}, q.minCap)
        return
    }
    if q.count == len(q.buf) {
        q.resize()
    }
}

func (q *Deque) resize() {
    newBuf := make([]interface{}, q.count<<1)
    if q.tail > q.head {
        copy(newBuf, q.buf[q.head:q.tail])
    } else {
        n := copy(newBuf, q.buf[q.head:])
        copy(newBuf[n:], q.buf[:q.tail])
    }

    q.head = 0
    q.tail = q.count
    q.buf = newBuf
}

func isPalindrome(head *ListNode) bool {
    var q Deque

    if head == nil {
        return true
    }
    node := head
    for node != nil {
        q.PushBack(node.Val)
        node = node.Next
    }

    for q.Len() > 1 {
        if q.PopFront() != q.PopBack() {
            return false
        }
    }

    return true
}

# Solution 4 - 런너를 이용한 우아한 풀이 

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        rev = None
        slow = fast = head
        # 런너를 이용해 역순 연결 리스트 구성
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
        if fast: # fast가 홀수인 경우
        	slow = slow.next

        # 팰린드롬 여부 확인 
        # 처음부터 절반까지 리스트 rev와 절반부터 끝까지 리스트 slow 비교
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev # 끝까지 가서 rev가 None이면 True 반환, 중간에 값이 달라서 while문 빠져나오면 False 반환

런너 (Runner) 기법 활용 ( 아래 설명 참고 )

느린 런너는 중간까지 이동하면서 역순 연결 리스트 rev를 만들어 나간다.

fast가 끝까지 가면 느린 런너는 중간까지 가고 이때 부터 비교한다.

처음부터 절반까지 역순 연결 리스트 rev와 절반부터 끝까지 남은 연결 리스트 slow 비교

 

다중 할당

rev, rev.next, slow = slow, rev, slow.next

 

만약 나눠서

rev, rev.next = slow,rev

slow = slow.next 

이렇게 할당하게 되면 rev와 slow는 동일한 객체를 참조하고 있기 떄문에 전혀 다른 결과가 나온다

 

ex) rev = 1 , slow = 2->3이라면

첫째 줄 실행시 rev = 2->3, 이고 rev.next = 1 이므로 rev  = 2->1 이 된다.

이때 rev는 slow와 같은 객체를 참조하고 있으므로 slow도 2->1이 된다

따라서 두번째 줄 실행시 slow = 1이라는 결과가 나오게 된다.

 

3개의 변수에 다중할당 했을 경우 

첫째 줄 실행시 rev = 2->1, slow = 3 ( 동시에 작업 실행)

 

---

# 연결 리스트

 :  데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.

동적으로 새로운 노드의 삽입, 삭제가 간편

연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉬움

서로 연결된 형태로 구성되어 있으며, 메모리 어딘가에 여기저기 흩뿌려진 형상을 띤다.

 

특정 인덱스에 접근 ( 탐색) O(n) 소요

시작 또는 끝 지점에 추가,삭제, 추출 작업은 O(1)

 

# 런너 기법 (Runner)

 : 연결 리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법

한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용

빠른 런너 (Fast Runner) , 느린 런너 ( Slow Runner )

빠른 런너가 2칸씩 이동, 느린 런너가 1칸씩 이동할 경우 빠른 런너가 끝에 도달하면 느린 런너는 중간 지점에 도달

 

# 다중 할당 (Multiple Assignment)

 : 2개 이상의 값을 2개 이상의 변수에 동시에 할당

'=' 연산자를 활용해 할당을 진행하면 값을 할당하는 것이 아니라 불변 객체에 대한 참조를 할당하게 된다.