反转链表

发表于 更新于

描述

给定一个单链表的头结点 pHead (该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围: 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n)

示例1

1
2
输入:  {1,2,3}
返回:  {3,2,1}

示例2

1
2
3
输入: {}
返回: {}
说明: 空链表则输出空

题解

newHead 表示已反转链表头部
pHead 表示当前链表发转的节点
pNext 表示未反转链表的头部保存

pHead 的下一个节点

当链表反转时,需如下步骤:

  1. 保存 pHead 的下一个节点. 防止后续链表丢失
  2. 将 pHead 指向 newHead ,完成节点反转
  3. 更新 newHead 为 pHead ,将完成的反转节点加入链表
  4. 更新 pHead ,继续反转依旧未反转的链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package main


type ListNode struct{
    Val int
    Next *ListNode
}


/**
 *
 * @param pHead ListNode类
 * @return ListNode类
 */
func ReverseList(pHead *ListNode) *ListNode {
	if pHead == nil || pHead.Next == nil {
        return pHead
    }

    var newHead *ListNode

    for pHead != nil {
        pHead, pHead.Next, newHead = pHead.Next, newHead, pHead
    }

    return newHead
}