算法:
反转链表的基本操作可以拆分成下面四步:
1.保存前序节点,
2.保存后续节点,
3.当前节点指向前序节点
4.偏移前序节点和当前节点
其他的变形题目,主要围绕两个关键点:
1.反转之后的前序节点的处理
2.反转之后的后续节点的保存
题目1:反转链表
https://leetcode-cn.com/problems/reverse-linked-list/
代码实现:
/*
解法:保存前序节点,
保存后续节点,
当前节点指向前序节点
偏移前序节点和当前节点
返回值 是前序节点
*/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var pre *ListNode
curr := head
for curr != nil {
// fmt.Println(":",*curr)
tmp := curr.Next
curr.Next = pre
pre = curr
curr = tmp
}
return pre
}
执行结果:
题目2:
https://leetcode-cn.com/problems/reverse-linked-list-ii/
代码实现:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if head == nil || head.Next == nil || m == n{
return head
}
first := head
var begin *ListNode
for i:= m; i>1; i-- { // 找到m节点的前序节点
begin = first
first = first.Next
}
var h1 *ListNode = first
for i:=n;i>m;i-- { // 找到第n个节点
h1 = h1.Next
}
var second *ListNode
if h1.Next != nil { // 找到第n个节点的后续节点
second = h1.Next
}
h1.Next = nil // 从n节点位置将链表分成两个单独的链表
// first为反转后的前序节点,second为反转之后的后续节点,
// 对于要反转的链表来说,second也是头节点的前序节点
h1 = reverseList(first,second)
if begin != nil {
begin.Next = h1
} else {
head = h1
}
return head
}
func reverseList(head *ListNode, last *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
curr := head
var pre *ListNode = last
for curr != nil {
tmp := curr.Next
curr.Next = pre
pre = curr
curr= tmp
}
return pre
}
/*
解法:将需要反转的单独拉出一个列表来操作
然后,将前面的初始位置记录一下
将结尾位置作为反转之后的pre节点连接起来
备注:需要注意传入的起始和结束位置为整个链表的情况
*/
执行结果:
题目3:两两交换链表中的节点 https://leetcode-cn.com/problems/swap-nodes-in-pairs/submissions/
代码实现:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 解法:递归,1st和2nd节点反转,1st节点的next指向反转之后的链表,2nd.Next指向1st作反转处理
func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// 两个临时节点定好位置
first := head
second:= head.Next
// 反转处理
first.Next = swapPairs(second.Next)
second.Next = first
return second
}
执行结果:
题目4:k个一组反转链表
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
代码实现:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
// 解法:递归,K个节点反转一次,然后头节点转换指向到下一个k链表,
// 循环直到都操作结束
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
begin,end := head,head
for i:=0; i<k;i++{
if end == nil { // 小于k的链表,直接返回
return head
}
end = end.Next
}
// end表示的是反转之后的头节点,其实就是k链表之后的那个节点
node := reverseList(begin,end)
// 更换头节点的指向,方便下一次反转链表
begin.Next = reverseKGroup(end,k)
return node
}
// 一个链表的反转,node表示反转之后的头节点
func reverseList(head *ListNode, node *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
curr:= head
pre := node
for curr != node {
tmp := curr.Next
curr.Next=pre
pre = curr
curr= tmp
}
return pre
}
执行结果: