关于链表:完虐算法反转链表

反转链表

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 = 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

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