反转链表

LeetCode206. 反转链表

问题描述

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。
示例:
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

分析问题

首先，我们按照题目的要求，先把图画出来，然后再分析。

image-20210906105355690

从图中我们可以看到，反转前和反转后指针的指向发生了反转。所以，我们在实现的过程中，我们可以通过调整链表的指针来达到反转链表的目的。

  1. 我们定义两个指针pre和cur。pre表示已反转部分的头结点，cur表示还没有反转部分的头结点。开始时cur=head，pre=None
  2. 每次让cur->next=pre，实现一次局部反转。
  3. 局部反转完成后，cur和pre同时向前移动一位。
  4. 循环上述过程，直到链表反转完成。

image-20210906143404239

代码实现

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

class Solution:
    def reverse(self, head):
        cur = head
        #初始化时，pre为None
        pre = None
        while cur:
            next=cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

head=ListNode(1,None)
cur=head
for i in range(2,6):
    tmp=ListNode(i,None)
    cur.next=tmp
    cur=cur.next

s=Solution()
pre=s.reverse(head)

while pre!=None:
    print(pre.val)
    pre=pre.next