단일 체인 테이블 반전 [python 실현]

단일 체인 테이블 반전 방법

첫 번째 노드가 옮겨다니기 시작하다

세 개의 지침으로 체인 시계의 반전을 해결한다cur는 현재의 체인 시계 노드이고 tmp 임시 저장cur.next, new_head은 이전cur

을 가리킨다.

그 중에서 tmp는 보존하기 전의 체인이 끊어지지 않는 것이 중요하다

끝 노드가 귀속되기 시작하다

귀속 반전 체인표, 귀속: 끝 노드에서 상급 노드를 가리키고, 상급 노드는 None을 가리키며, 이 과정을 반복하여 귀속이 끝날 때까지

코드는 다음과 같습니다.

class ListNode:

    def __init__(self, val):
      self.val = val
      self.next = None


class Solution:
    
    def reverse_list(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head

        #  ，cur ，tmp cur.next，new_head cur 
        cur = head
        tmp = None
        new_head = None
        while cur:
            tmp = cur.next
            cur.next = new_head
            new_head = cur
            cur = tmp

        return new_head       
    
    def reverse_list2(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        #  Node head 
        Node = None
        while head:
            p = head
            head = head.next
            p.next = Node
            Node = p
        return Node
    
    def reverse_list_recusive(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        #  ， ： ， None， ， 
        NewHead = self.reverse_list_recusive(head.next)
        head.next.next = head
        head.next = None
        return NewHead
        

if __name__ == "__main__":
    n1 = ListNode(1)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n4 = ListNode(4)

    n1.next = n2
    n2.next = n3
    n3.next = n4

    new_head = Solution().reverse_list(n1)
    print(new_head.val)
    print(new_head.next.val)
    print(new_head.next.next.val)
    print(new_head.next.next.next.val)

    print()

    new_head = Solution().reverse_list2(new_head)
    print(new_head.val)
    print(new_head.next.val)
    print(new_head.next.next.val)
    print(new_head.next.next.next.val)

    print()

    new_head = Solution().reverse_list_recusive(new_head)
    print(new_head.val)
    print(new_head.next.val)
    print(new_head.next.next.val)
    print(new_head.next.next.next.val)

THE END

이 문제는 각 공장의 필기시험 문제와 면접 문제에 자주 등장한다. 평소에 사람들은 체인 시계를 거의 사용하지 않을 것이다. 그러나 면접에서 자주 시험을 보기 때문에 체인 시계의 성질과 체인 시계를 어떻게 반전시키는지 주의해야 한다.