실패자에 가입하여 우리는 체인 논리를 하고 있다

좋습니다. 만약 당신이 개인적으로 이런 가소로운 복잡한 데이터 구조에 상처를 입은 적이 있다면 손을 들어 주십시오.

그래, 이게 좀 드라마틱할지도 모르지만, 내가 불가능한 시간 안에 해결 방안을 생각해 내야 했던 몇 번(또는 30번)에서 나는 확실히 내가 상처를 받았다고 느꼈다.자신의 논리에 따라 관찰되고 판단될 수 없는 압력을 더해보자.만약 네가 나처럼 된다면, 너는 아마 좀 울 것이다...몇 번?
그러나 내가 가장 좋아하는 철학가인 론 스완슨의 말로 말하자면, "당신의 눈물을 당신의 눈에 남겨두고 당신만의 곳에 두어라."
내가 이 글을 쓴 것은 초보자들을 위해서이다. 그들은 가시화 해결 방안, 이를 위조 코드로 전환한 다음에 작업 해결 방안을 작성하는 데 어려움이 있다.
본고에서 나는 체인 시계가 무엇인지, 왜 이렇게 사람을 곤혹스럽게 하는지, 그리고 어떻게 교묘하고 교묘하게 노드와 지침을 안배하여 지금까지 내가 본 가장 흔히 볼 수 있는 체인 시계 문제 중 하나인 반전 체인 시계를 해결할 것인가를 소개할 것이다.
먼저 체인 테이블의 다음 클래스 정의를 살펴보겠습니다.

# Definition for singly-linked list.

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

*이것은 체인 테이블을 정의하는python 방식으로, 직접 LeetcodeAdd Two Numbers의 도전에서 나온 것이다

그러면 ListNode입니까 아니면 노드 목록입니까?

체인 시계를 만들려면 값을 저장하고 다른 값을 가리키는 것이 필요합니다.우리는 이 실례를 목록 노드라고 부르거나 노드라고 부른다.
체인 시계라는 이름 자체는 사실상 리스트가 아니기 때문에 곤혹스럽다.적어도 Python의 목록이나 JavaScript의 배열과는 달리 색인을 포함하기 때문에 질서정연합니다.
체인 테이블은 값을 저장하여 체인처럼 연결하는 방법이다.이것은 시작과 끝 노드에 대응하는 머리와 꼬리 속성을 가진 클래스로 정의할 수 있지만, 항상 그렇지는 않다.
기술적으로 말하자면, 단지 하나의 노드가 체인 테이블이다. 설령 그것이 None 값을 가리킨다 하더라도.
예를 들어, 위의 클래스를 사용하여 체인 테이블을 만듭니다.

linked_list = ListNode(1)

print(linked_list) 
# this is what it would look like printed to the terminal: 
# <class ListNode object> 

# to access the data
linked_list.val   # 1
linked_list.next  # None

우리의 linked_ 목록은 다음과 같습니다.# 1 -> None정말이지, 이게 뭐야?개미 명단?적어도 필요해...이거보다 세 배?!
하하, 아니, 이 정도야.노드를 계속 생성한 다음 연결할 수 있습니다.

node2 = ListNode(2)
linked_list.next = node2
# or simply: 
node2.next = ListNode(3)

지금 우리가 그것을 그려내면 우리의 전체 체인 시계는 이렇게 보일 것이다.# 1 -> 2 -> 3 -> None그러나 linked_list 은 여전히 val (1) 과 next (node2) 을 가진 단일 노드일 뿐이다.
많은 곤혹은 목록이 없다는 사실에서 비롯되기 때문에 모든 노드의 값을 얻는 것은 좋은 ol'for 순환을 작성하는 것과 같지 않다.대부분의 경우, 시작 노드에 대한 인용만 얻을 수 있습니다.시작 노드만 있으면 모든 노드를 훑어볼 수 있다.

체인 시계를 두루 훑어보다

순환에 대해서?우리가 가야 할 곳은 돌아갈 필요가 없다!시작 노드를 지정합니다. 다음 노드, 다음 노드 이후의 노드와 모든 다른 노드에 도달하려면 반복해야 합니다.

# start with the given node
curr = node     

    # while loop that keeps going as long as current never becomes NONE
    while curr is not None:

        # do something with this node's value or pointer
        # this will be where we do the logic to reverse
        print(curr.value)       

        curr = curr.next # set the curr pointer to next node

많은 LL 문제에서 당신은 이gem-of-a-while 순환을 자주 사용하기 때문에 손등처럼 그것을 연습하고 이해해야 합니다!

링크 목록 반전

구글에서 이 알고리즘을 검색하면 다음과 같은 결과를 볼 수 있다.

Initialize three pointers prev as NULL, curr as head and next as NULL.
Iterate through the linked list. In loop, do following. 
// Before changing next of current, 
// store next node 
next = curr->next
// Now change next of current 
// This is where actual reversing happens 
curr->next = prev 
// Move prev and curr one step forward 
prev = curr 
curr = next

*Geeksforgeks의 알고리즘입니다.조직:
내가 일찍이 네가 이 문제를 몇 번 해결할 수 있다고 생각했던 것을 범하지 말고 그것을 기억해라.당신은 한 인터뷰에서 "일단 내가 지시를 좀 했다. 그리고 나는 간단하게 이 지침을 이 지침의 다음 바늘과 이전 바늘을 현재의 다음 바늘로 설정했다. 아니면 위의 바늘인지 다음 바늘인지 설정했다. 찍어라. 기억이 나지 않는다."라고 말한 것을 발견할 수 있다.
실제로 유일하게 기억해야 할 것은 체인 시계를 교체하려면 세 개의 다른 바늘이 필요하다는 것이다.
그리고 정확하게 반전하는 방법을 기억하지 못하더라도 바늘을 움직여 해결할 수 있다.가능한 한 많은'답안 찾기'를 연습해야지, 위조 코드를 보지 마라.나에게 있어서, 이해하는 것은 그것을 상상하는 것을 의미한다.

어떻게 가시화 해결 방안을 코드로 바꿉니까

1) 시작점을 찾아라. 즉, 1>2->가 없으면 시작값은prev = None, curr = 1, and next = None

그림 1
2) 모든 것을 그려라.다음을 포함합니다.

노드와 다음 포인터 (검은 화살표가 있는 원으로 그려집니다)

모든 값 없음

이전, 현재 및 다음 포인터(내 색상 인코딩)

순환이 시작될 때마다prev,curr,next값

및 각 회로 시작 조건

그림 2:
3) 화살표가 목록을 반전시키기 위해 무엇을 가리키는지 찾아낸다.노드를 이동하지 않고 화살표만 이동해야 합니다.화살표를 이동하기 전에 이 단계를 코드로 작성할 수 있는지 확인하십시오.예를 들어 이 예에서 우리는 next 바늘을 제외한 모든 컬러 바늘이 그들이 필요로 하는 위치에 있다는 것을 안다.빨간색 화살표가 2를 가리키려면 논리는'next=curr'입니다.다음
우리는 목록을 처리하는 것이 아니기 때문에 next + 1나 next[1] = 20 같은 것만 말할 수 없다.우리는 기존의 지침을 사용하여 사방으로 이동하거나 노드에 도달할 수 있을 뿐이다.
4) 새 순환에 들어가기 전에prev,curr,next 값의 값(그림2 밑에 있는 값)을 화살표가 가리키는 위치로 업데이트합니다.
5) 새 순환이 시작될 때 첫 번째 순환으로 작성된 코드를 검사하여 논리가 여전히 적용되고 기대 효과에 도달하도록 한다.
내가 이걸 어떻게 하는지 영상으로 봐.
진정으로 한 걸음 한 걸음 따라가서 아무런 도움 없이 스스로 그것을 그려 보세요.화살표를 지우고 다시 그려야 하기 때문에 백판이나 연필 한 자루가 도움이 될 것이다.이것은 연습, 인내심, 반복이 필요하다.내가 이 동영상을 녹화하기 전에, 나는 나의 절차를 삭제하고, 적어도 세 번, 네 번을 시작했다.때때로, 논리는 첫 번째 순환에서 작동하지만, 계속 실행할 때, 위조 코드가 더 이상 작동하지 않을 것이라는 것을 깨닫게 됩니다.괜찮아, 아무 일도 이루지 못했다고 생각하면 천천히 해, 5분만 쉬어.
여기 끝에 있는 역방향 목록의 시작 노드가 prev 포인터 변수를 통해 접근할 수 있음을 알 수 있습니다.이것은 우리가 되돌아오고 싶은 값이다.

우리 계속 인코딩합시다!

코드:

class Solution:
    def reverseList(self, head):
        prev = None 
        curr = head
        nxt = None
        while curr is not None:
            nxt = curr.next

            # // This is where actual reversing happens 
            curr.next = prev

            prev = curr
            curr = nxt

        return prev

테두리 상황이 우리의 코드를 파괴할 수 있다. 그것은 우리가 None 값을 전송하거나, 다시 말하면 빈 목록을 매개 변수로 삼는 것이다.우리는 하나의 조건으로 이 문제를 해결합시다.

class Solution:
    def reverseList(self, head):
        if head is None:
            return head

        prev = None 
        curr = head
        nxt = None

        while curr is not None:
            nxt = curr.next

            # This is where actual reversing happens 
            curr.next = prev

            # then we update values to traverse
            prev = curr
            curr = nxt

        return prev

배달

체인 시계 문제는 면접에서 흔히 볼 수 있는 도전으로 처음에는 곤혹스러울 수 있기 때문에 가능한 한 체인 시계를 많이 사용하는 연습을 한다.

논리를 기억하려 하지 마라. 논리는 혼란을 일으킬 수도 있고, 항상 똑같은 도전도 하지 않을 것이다.가장 좋은 방법은 노드를 편안하게 그리고 시각 보조 도구를 만드는 것이다.

목록을 반복할 때 3개의 포인터가 필요합니다. PREV, CURR, NEXT입니다.

만약 네가 《나쁜 여자》를 보지 않았다면, 너는 상징적인 영화 한 편을 놓쳤을 것이다. 너는 마땅히 보러 가야 한다.체인 시계의 반전을 파악한 후에야 말이다.

나는 네가 이 문장이 도움이 된다고 생각하고 나의 유행 문화 영화를 참고하기를 바란다.나는 영화의 인용에 적응할 똑똑한 방법이 거의 없지만, 나는 당신들에게 체인 시계나 각박한 여자와 무관하게 오래된 경전을 남겨 줄 것입니다.그것은 심지어 여기에 있지 않기 때문에 우리와 함께 앉을 수 없다.
네, 정말입니다. 그것은 꼴찌에서 두 번째입니다.
생활 리듬이 매우 빠르다.만약 네가 가끔 멈추어 사방을 둘러보지 않는다면, 너는 그것을 놓칠 수도 있다.
Ferris Bueller의 휴일.