Skip to main content

206. Reverse Linked List

分析

注意写迭代法的时候,每一次行为注意会失去什么

递归的写法关键是理解清楚定义,这里讲的很清楚了 :递归讲解 输入一个节点 head,将「以 head 为起点」的链表反转,并返回反转之后的头结点

Pasted image 20220423152232.png

Pasted image 20220423152246.png

题解

迭代

// 1 -> 2 -> 3
// null -> 1
// null -> 2 -> 1
func reverseList(head *ListNode) *ListNode {
p, dummyHead := head, &ListNode{}

for p != nil {
dummyHeadNext := dummyHead.Next
dummyHead.Next = p
pNext := p.Next
p.Next = dummyHeadNext

p = pNext
}

return dummyHead.Next
}

递归

/**
* 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
}

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