面试：反转链表

题目：反转链表

要求：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

反转链表算是面试中比较常见的一个关于链表的题，整体上难度不大，但如果你能掌握多种的解法，往往可以让面试官眼前一亮

注意提醒一点，在面对链表的面试题时，建议多画一下图理解一下

解法 1：简单双指针

image

通过双指针，遍历 head 指针，通过中间变量，逐步指向新的 head 节点，完成链表反转

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    var newHead *ListNode
    for head != nil {
        node := head.Next
        head.Next = newHead
        newHead = head
        head = node
    }

    return newHead
}

结果如下：

image

还有一种简化的写法，在同一步操作中，改变各个变量对应的值，可以省去中间变量，但这样阅读其实并不友好

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    var newHead *ListNode
    for head != nil {
        head, head.Next,newHead = head.Next, newHead, head
    }

    return newHead
}

image

解法 2：递归

整体思路是递归到最后一个节点，这个节点就是链表反转后的头节点，这里记作 ret，最终只需要返回这个 ret 指针即可，剩余的都是对中间数据进行指针反转。

具体要怎么分析呢？这样就要画个图了

image image

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    ret := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return ret
}

递归去做其实不太容易理解，但也不失为一个巧妙的方法：

image

解法 3：双头指针

这个解法是参考 leetcode 大神的题解的，跟双指针的解法有点像，但更巧妙

image

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    cur := head
    for head.Next != nil {
        t := head.Next.Next
        head.Next.Next = cur // 反转原指针方向
        cur = head.Next // 将新头节点移到下一位
        head.Next = t // 连接回断开的地方，继续重复上面操作
    }

    return cur
}

效果跟简单的双指针没差多少：

image

欢迎关注公众号：若鱼治水，文章会首发在公众号，也可备注加我备注进群进技术交流群～