链表反转面试题
链表反转-基础篇
题目
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例：
输入: 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 }