题目描述

输入一个链表,反转链表后,输出新链表的表头。

  • 示例1

输入

1
{1,2,3}

输出

1
{3,2,1}

直观来看对于链表:

01

反转后

1

常规解法

  1. 其实我们本质上是把每个节点的数据之间的指向调整一下

3

  1. 通常我们使用preNode(前一个节点),currNode(当前节点),nextNode(当前节点)来实现遍历每个节点修改。最开始preNode指向null,currNode与nextNode指向第一个节点。

  1. 现在开始第一个反转:

    将nextNode指针指向下一个节点

    修改当前指针的方向

    方向修改完成,将pre指向当前节点

    将当前节点移动到下一个节点上

  2. 直到currNode不为null。总结来说preNode用来维持与已经反转好的那部分的关系,nextNode是为了currNode完成方向逆转之后跳到下一个节点,currNode完成方向逆转,承接preNode。想一想如果没有nextNode行不行?

源码(golang)

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
29
30
31
32
33
34
35
36
37
38
39

// Link 链表
type Link struct {
Value int
Next *Link
}

/*
> preNode, curNode, nextNode
1. nextNode = curNode.Next
2. curNode.Next = preNode
3. preNode = curNode
4. curNode = nextNode
*/
// ReversalLink 反转链表
func ReversalLink(head *Link) *Link {
if head == nil {
return nil
}

if head.Next == nil {
return head
}

var preNode *Link
var nextNode *Link

for head != nil {
nextNode = head.Next
head.Next = preNode
preNode = head
head = nextNode
}

return preNode

}


递归解法

  1. 以heap为起点进行反转,然后返回新链表的起点元素。

  1. 注意第一个元素需要做单独处理

源码(golang)

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

// Link 链表
type Link struct {
Value int
Next *Link
}

// ReversalLinkRecursion 递归反转全部链表
func ReversalLinkRecursion(head *Link) *Link {
if head == nil {
return nil
}

if head.Next == nil {
return head
}
fmt.Println("bbbb")

lastLink := ReversalLink(head.Next)
fmt.Println("aaaa")
head.Next.Next = head
head.Next = nil
return lastLink
}