【日拱一卒】链表——链表反转

需求

实现链表的反转

输入：1->2->3->4->5

输出：5->4->3->2->1

难点

如果换成数据反转，你会吗（傻子才不会）。

按照常规思维，链表反转需要知道最后一个元素，然后从最后一个元素依次往前找，直到遍历到第一个元素即完成反转。

但是这里并不是双向链表，即使找到最后一个元素也找不到前继节点。再者，即使是双向链表，通过找到尾结点再往回遍历听着也不像是很高端的做法。

思路

除了找到尾结点进行反转的思路，我们是否可以考虑，在遍历的同时就去做反转的操作，类似

1->2->3->4->5

2->1->3->4->5

3->2->1->4->5

4->3->2->1->5

5->4->3->2->1

直觉告诉我们，肯定没问题，但是具体怎么做呢，看图

第一步：画出输入链表结构

image.png

第二步：初始化

image.png

注意

为了不干扰head指针，重新定义一个新的cur指针，用于后面的遍历。pre指针表示最终反转后的链表指针
指针存储了指向变量的地址，比如这里的cur存储的是head.next的地址

第三步：将1节点的next指向pre（即null）

image.png

注意

此时的pre指向的是一个null的地址，需要注意的是pre是一个指针，pre还可以指向其他节点（参见下一步操作）

第四步：将pre指向1节点

image.png

注意

将pre指向指向节点1，pre之前指向的是null，现在指向节点1，所以图中虚线部分的连接就不存在了
这时候，我们成功的将第一个节点纳入最终反转链表pre中

第五步：解决指针丢失问题

按照前面几步的思路，我们依次遍历后面的节点，并对遍历的节点做如上步骤的处理，这样，最终我们就会得到反转后的链表pre。

但是，这里有个指针丢失的问题。

原来cur指向节点1，cur.next指向节点2，但是在第三步的时候将cur.next指向了null。所以使用cur.next就无法满足我们遍历节点2的需求了。

这时候，我们需要一个新指针，用来保证链表遍历的时候不会断掉，如下图

image.png

注意

这里next指针需要在第二步初始化的时候就做好，不然这时候做next=cur.next就无法指向节点2了

第六步：开启下一次迭代

image.png

注意

cur作为一个哨兵节点，指向节点2，开始像处理节点1一样处理节点2，直到遍历完所有节点

代码实现

版本1

func reversrList(head *ListNode) *ListNode {
    cur := head
    var pre *ListNode = nil
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

对照该代码实现和上面几个步骤，基本就可以摸透链表反转的思路了。

这里还有一个更加简洁的代码实现

版本2

func reversrList(head *ListNode) *ListNode {
    cur := head
    var pre *ListNode = nil
    for cur != nil {
        pre, cur, cur.Next = cur, cur.Next, pre
    }
    return pre
}

个人感觉不是很好理解，所以将其拆解成上面的代码实现。

不忘初心

老王：你不好好种地，你以后长大能干什么

小王：学算法

老王：学算法？！你数组、链表、栈、队列、堆、排序、查找都整不明白，你学什么算法

小王：我只学链表反转

老王：。。。