题解 | #反转链表#

一、python链表结构

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

二、输入，输出

输入：链表头结点

输出：反向链表的头结点

@param head ListNode类 
@return ListNode类

三、解题思路

1. 要区分!=None与not,均可以，但易错。

2. 算法流程图解

3. 要注意先判断head==None和head.next==None

!=None的写法:

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        # write code here
        
        if head==None:
            return None
        if head.next==None:
            return head
        
        leftPointer=head
        midPointer=head.next
        rightPointer=head.next.next
        leftPointer.next=None
        
        while rightPointer!=None:
            midPointer.next=leftPointer
            leftPointer=midPointer
            midPointer=rightPointer
            rightPointer=rightPointer.next
        
        midPointer.next=leftPointer
        return midPointer

not的写法:

class Solution:
  def ReverseList(self , head: ListNode) -> ListNode:
      # write code here
      
      if not head:
          return None
      if not head.next:
          return head
      
      leftPointer=head
      midPointer=head.next
      rightPointer=head.next.next
      leftPointer.next=None
      
      while rightPointer:
          midPointer.next=leftPointer
          leftPointer=midPointer
          midPointer=rightPointer
          rightPointer=rightPointer.next
      
      midPointer.next=leftPointer
      return midPointer