链表反转
LC 206. Reverse Linked List 反转链表
https://leetcode.com/problems/reverse-linked-list/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
prev := (*ListNode)(nil)
for head != nil {
next := head.Next
head.Next = prev
prev = head
head = next
}
return prev
}
递归解法
待复习
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil {
return nil
}
if head.Next == nil {
return head
}
next := head.Next
newHead := reverseList(next)
next.Next = head
head.Next = nil
return newHead
}
反转链表前 N 个节点
func reverseN(head *ListNode, n int) *ListNode {
oldHead := head
prev := (*ListNode)(nil)
for i := 0; i < n; i++ {
next := head.Next
head.Next = prev
prev = head
head = next
}
newNext := prev
oldHead.Next = head
return newNext
}
LC 92. Reverse Linked List II 反转链表 II
https://leetcode.com/problems/reverse-linked-list-ii/
待复习
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if left == 1 {
return reverseN(head, right-left+1)
}
h := head
prev := (*ListNode)(nil)
for i := 1; i < left; i++ {
prev = h
h = h.Next
}
newPartHead := reverseN(h, right-left+1)
prev.Next = newPartHead
return head
}
func reverseN(head *ListNode, n int) *ListNode {
oldHead := head
prev := (*ListNode)(nil)
for i := 0; i < n; i++ {
next := head.Next
head.Next = prev
prev = head
head = next
}
newNext := prev
oldHead.Next = head
return newNext
}