링크 반전 [도해]

링크 의 머리 결 점 을 제시 하고 링크 를 반전 시 킨 후 새로운 머리 결 점 으로 돌아 갑 니 다.
먼저 이 체인 헤드 노드 [pHead] 가 왼쪽 에 있다 고 가정 하고 꼬리 노드 는 오른쪽 에 세 개의 지침 을 설정 합 니 다. tmp, p, q 그 중에서 tmp 와 q 두 개의 지침 은 계속 뒤로 이동 하고 p 지침 은 원래 의 노드 위치 에 정 해 져 있 지만 next 는 tmp 와 q 지침 을 따라 계속 이동 합 니 다.

tmp      q
 @   ——> @  ——> @  ——> @  ——> @       
 p

첫 번 째 단 계 는 p 포인터 의 Next 를 바 꾸 어 p 의 next 를 가리 키 고 q 포인터 의 next 를 tmp 로 반전 시 킵 니 다.

tmp     q
  /```````````\
 @   @  ——> @      
 p

두 번 째 단 계 는 tmp 지침 을 q 지침 의 위치 로 이동 시 키 고 q 지침 을 p - > next 위치 로 이동 합 니 다.

       tmp     q
  /```````````\
 @   @  ——> @      
 p

이때 우 리 는 이미 초기 상태 가 나 타 났 다 는 것 을 알 게 되 었 습 니 다. 첫 번 째 단 계 를 반복 해서 p - > next 를 q - > next 로 가리 키 고 q - > next 의 지침 을 tmp 에 반전 시 켰 습 니 다.

       tmp     q
  /``````````````````\
 @  @      
 p

tmp 와 q 바늘 을 계속 뒤로 이동 하면 두 번 째 단 계 를 반복 하 는 것 과 같 습 니 다.

              tmp     q
  /``````````````````\
 @  @      
 p

첫 걸음 을 되풀이 하 다

             tmp     q
  /`````````````````````````\
 @ 

tmp 포인터 와 q 포인 터 를 계속 뒤로 이동 합 니 다.

                    tmp      q
  /`````````````````````````\
 @ 

이때 우 리 는 p 포인 터 를 링크 의 꼬리 부분 으로 옮 겼 습 니 다. q - > next 가 비어 있 으 면 p 를 q 의 next 로 직접 가리 키 고 이 를 NULL 로 만 들 었 습 니 다. 원래 의 노드 에서 꼬리 노드 로 바 꾸 었 습 니 다. q 포인터 가 노드 를 가리 키 는 next 가 tmp 로 반전 되 었 기 때문에 마지막 노드 의 포인 터 도 반전 되 었 고 새로운 머리 결점 이 탄생 했 습 니 다.q 가 빈 포인터 로 계속 이동 할 수 없 기 때문에 while 순환 이 종료 되 고 tmp 가 정상 적 인 후에 q 노드 로 이동 하여 tmp 포인터 즉 반전 후의 머리 결 점 지침 을 되 돌려 줍 니 다.[여 기 는 분명히 tmp 와 q 포인터 가 같은 위 치 를 가리 키 고 있 는데 왜 tmp 지침 을 되 돌려 줍 니까? 링크 가 한 노드 만 있 을 때 q 는 빈 지침 이 고 tmp 는 두 결점 입 니 다. 그러면 한 가지 상황 을 반영 합 니 다. 즉, 한 노드 만 있 고 두 결점 은 바로 끝 노드 입 니 다. 반전 후에 변 하지 않 고 순환 이 들 어가 지 않 고 초기 tmp, 즉 두 결점 으로 돌아 갑 니 다. q 지침 은 다 릅 니 다.가리 키 는 것 은 빈 지침 입 니 다. 머리 결점 을 가리 키 지 않 았 기 때문에 q 지침 으로 돌아 갈 수 없고 tmp 로 돌아 가 야 합 니 다]

NULL                       tmp
 ↑                          q
 @ 

코드 는 다음 과 같 습 니 다:

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)return pHead;
        ListNode* p=pHead;
        ListNode* q=pHead->next;
        ListNode* tmp=pHead;
        while(p->next!=NULL)
        {
            p->next=q->next;
            q->next=tmp;
            tmp=q;
            if(p->next==NULL)break;
            q=p->next;
        }
        return tmp;
    }
};

또 다른 서법, 가장 보편적 인 세 가지 지침 법.또한 잘 이해 할 수 있 습 니 다: 현재 결점 의 다음 즉 pNext 현재 결점 의 이전 즉 pPrev 현재 결점 즉 pNode 는 현재 결점 의 다음 을 저장 하고 비어 있 는 지 판단 하면 현재 결점 이 뒤 집 힌 후 링크 의 첫 번 째 노드 를 현재 노드 의 mpNext 포인 터 는 이전 노드 pPrev 를 가리 키 며, 이전 노드 포인 터 를 가리 키 는 후 현재 노드 로 옮 기 고, 현재 노드 포인 터 를 다음 노드 로 가리 키 며, 상기 절 차 를 반복 합 니 다.

ListNode* ReverseList(ListNode* pHead)
{
    ListNode* pRevesedHead=nullptr;
    ListNode* pNode=pHead;
    ListNode* pPrev=nullptr;
    while(pNode!=nullptr)
    {
        ListNode* pNext=pNode->m_pNext;
        if(pNext==nullptr)pRevesedHead=pNode;
        pNode->m_pNext=pPrev;
        pPrev=pNode;
        pNode=pNext;
    }
    return pRevesedHead;
}

python 의 바보 변수 판

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head ==None:
            return head
        tmp=head.next 
        pre=None
        ans=head
        while tmp!=None:
            tmp=head.next
            if tmp==None: ans=head
            head.next=pre
            pre=head
            head=tmp
        return ans