소 객 - 검 지 offer 시리즈 문제 풀이 & LeedCode 바이트 댄스 기업 면접 문제 라 이브 러 리 중 하나: 반전 링크

1. 문제 설명: 링크 를 입력 하고 링크 를 반전 시 킨 후에 새로운 링크 의 헤더 를 출력 합 니 다.
2. 데이터 구조: 링크
3. 문제 풀이: 방법 1: 쌍 지 침 법 반전 은 두 걸음 이 필요 합 니 다. 첫 번 째 단 계 는 그의 결점 을 찾 고 두 번 째 단 계 는 결점 을 바 꾸 면 됩 니 다.그 다음 에 결점 을 이 원소 의 자체 로 할당 해 야 한다.
순환: 원소 결점 이 가리 키 는 원 소 를 찾 습 니 다. 목 표 는 원소 결점 이 가리 키 는 원 소 를 자신 자신 으로 바 꾸 는 것 입 니 다.

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    #   ListNode
    def ReverseList(self, pHead):
        #                  ，                 ，              none
        #             pHead
        if not pHead or not pHead.next:
            return pHead
        #           ，               none                 none
        last = None

        #          pHead      
        while pHead:
            #                 ，         
            temp = pHead.next
            """
                                    .
                                      .

            """
            #                       none last        none (          last)
            #                   pHead          last,
            pHead.next = last
            #        pHead           last
            # last  pHead        ,
            last = pHead
            #   pHead          None  
            pHead = temp

        return last

방법 2: 세 손가락 침 법 1 은 기 존의 머리 를 꼬리 로 바 꾸 고 꼬리 의 next 는 비어 있 습 니 다. 2 번 째 node 부터 순환 하여 next 를 앞 3 을 가리 키 려 면 반전 되 지 않 은 링크 의 머리 를 가리 키 는 지침 이 있어 야 합 니 다.

class Solution:
    #   ListNode
    def ReverseList(self, pHead):
        #        ，    
        if pHead == None:
            return None
        #           
        if pHead.next == None:
            return pHead
        #               
        leftPointer = pHead
        #               
        midPointer = pHead.next
        #                          
        rightPointer = midPointer.next
        #               ，       next   None；
        leftPointer.next = None
        #   ，                      ，        ，       。
        while rightPointer:
            #                  leftPointer
            midPointer.next = leftPointer
            #          。     。
            #                     
            leftPointer = midPointer
            #              ，          
            midPointer = rightPointer
            #            ，           。
            rightPointer = rightPointer.next
        #                      ，                                。
        midPointer.next = leftPointer
        #             ，                 ，  。
        return midPointer

4. 복잡 도 분석:
방법 1: 시간 복잡 도: O (N) 공간 복잡 도: O (1) 방법 2: 시간 복잡 도: O (N) 공간 복잡 도: O (1)