反转链表

LeetCode206. 反转链表

问题形容

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

剖析问题

首先，咱们依照题目的要求，先把图画进去，而后再剖析。

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

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

代码实现

class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = nextclass Solution:    def reverse(self, head):        cur = head        #初始化时，pre为None        pre = None        while cur:            next=cur.next            cur.next = pre            pre = cur            cur = next        return prehead=ListNode(1,None)cur=headfor i in range(2,6):    tmp=ListNode(i,None)    cur.next=tmp    cur=cur.nexts=Solution()pre=s.reverse(head)while pre!=None:    print(pre.val)    pre=pre.next

更多算法题解，关注公众号《程序员学长》，欢送退出。