反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

方法1：双指针

1
2
3
4
5
6
7
8
9
10
func reverseList(head *ListNode) *ListNode{
    pre := &ListNode{}   //先定义一个空
    cur := head
    for cur!=nil{
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp 
    }
}

思路

（nil）->A ->B->C->D->nil 反转后就变成 nil<-A<-B<-C

这边的思路就是把指针反转，非常经典的一前pre一后cur双指针问题，链表很有用

根据规律可得一般来说处理一个链表当前结点cur的时候往往需要一个指向上一个结点的指针pre

先看第一步 pre是cur的前一个指针，temp是作为指针的替代者（等会就知道了）

一开始pre是nil，cur是A，但是这是特殊情况先不看

假设pre是A，cur是B，如果反转两者的指针使得cur指向pre，可以直接cur.next=pre

但是你会发现如此操作后应该指向C的指针（cur.next）没了

也就导致了cur无法移动C了，进入死循环

因此需要一个temp指针暂时存放cur.next来指向C

等A,B之间的交换完成后，pre和cur分别往右边移动一格

temp := cur.Next 存放指向C结点的指针

cur.next=pre 使得B指向A

pre = cur pre指针指向B

cur =temp cur指针指向C

为什么一开始pre要是空，因为反转后最后指针指向空

方法二：递归

递归的思路与双指针一毛一样，但是反正会了双指针的思路也写不出递归，只能说递归太傻逼，而不是我太笨

1
2
3
4
5
6
7
8
9
10
11
12
func reverseList(head *ListNode) *ListNode {
    return help(nil, head)
}

func help(pre, head *ListNode)*ListNode{
    if head == nil {
        return pre
    }
    next := head.Next
    head.Next = pre
    return help(head, next)
}

总结

  1. 链表设两个指针一前一后，后面是正在处理的指针真的非常好用
  2. 链表处理的承载是指针，而不是结构体，主要是要处理好指针的关系，所以命名类型的时候一般是直接指针走你