链表反转-基础篇
题目
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
考察要点
- 链表的熟悉程度
- 迭代法和递归法两种实现思路
迭代法:
- 优点:效率高,运行时间只随循环的增加而增加;无额外开销;
- 缺点:代码难理解;代码不如递归代码简洁;
递归法:
- 优点:用有限的循环语句实现无限集合;代码易读;大问题转化成小问题,减少代码量;
- 缺点:递归不断调用函数,浪费空间;容易造成堆栈溢出。
- 复杂度:时间复杂度O(N),空间复杂度O(1)
解法1:迭代法
通过双指针,遍历 head 指针,通过中间变量,逐步指向新的 head 节点,完成链表反转
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
}
解法2:递归法
整体思路是递归到最后一个节点,这个节点就是链表反转后的头节点,这里记作 ret,最终只需要返回这个 ret 指针即可,剩余的都是对中间数据进行指针反转。
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
}
链表反转-进阶篇
题目
反转从位置 m 到 n 的链表. 请使用一趟扫描完成反转.
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
考察要点
- m和n之间的反转与基础篇一样
- 在m的边界处理,m-1的next指向n;m的next指向n+1
在n的边界处理,n的next指向n-1;
解法1:迭代法
func reverseBetween(head *ListNode, m int, n int) *ListNode {
dummy := ListNode{Val: 0}
dummy.Next = head
node := &dummy
for i := 1; i < m; i++ {
node = node.Next
}
pre := node
curr := node.Next
tail := curr
for i := m; i <= n; i++ {
nxt := curr.Next
curr.Next = pre
pre = curr
curr = nxt
}
tail.Next = curr
node.Next = pre
return dummy.Next
}
解法2:递归法
type ListNode struct {
Val int
Next *ListNode
}
func rev(root *ListNode) *ListNode {
if root == nil || root.Next == nil {
return root
}
last := rev(root.Next)
root.Next.Next = root
root.Next = nil
return last
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
d := &ListNode{
Val: 0,
Next: head,
}
h := d
tmp := head
var leftNode *ListNode
var rightNode *ListNode
var prevNode *ListNode
var nextNode *ListNode
foundLeft := false
foundRight := false
count := 1
_ = rightNode
for tmp != nil {
if foundLeft && foundRight {
break
}
if count == left {
leftNode = d.Next
d.Next = nil
prevNode = d
foundLeft = true
}
if count == right {
rightNode = tmp
nextNode = tmp.Next
tmp.Next = nil
foundRight = true
}
count++
d = tmp
tmp = tmp.Next
}
last := rev(leftNode)
prevNode.Next = last
leftNode.Next = nextNode
return h.Next
}