AK F.*ing leetcode 流浪计划之链表
字节员工,直播业务长期招人(北京,杭州,上海,深圳),hc巨多,社招,校招,实习都有。
欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。
@[toc]
一、简介
在leetcode里链表问题大部分是基础的模拟题,题目解题思路的理解和思考并不难,这类题目的难点在于对边界情况的考虑。面试中出这类题目,往往是考查应试者测试用例设计能力和考虑问题的全面性。想要写出准确、简短的代码,需要平时对固定的操作原理及代码了然于心,用到时做到胸有成竹,处变不惊。
本文将介绍单链表的常用操作及其应用,对于双链表部分由于题目较少,原理也与单链表类似,只介绍双链表插入部分。
由于带头结点可以简化很多边界问题,我喜欢把无头结点的链表前面加一个头结点再进行处理。
本文原理参照严版《数据结构与算法》,公众号内回复“数据结构”可以获取pdf电子版。
二、作用
- 链表常规操作,增,删,改,查
- 判断是否有环路(快慢指针)
- 查询倒数第K个结点(跟车算法)
- 综合上述基础操作,可以组合出更复杂的操作。
三、方法定义及算法
单向链表
一个结点定义为Node
type Node struct { Val int // 值 Next *Node }
一个链表定义为List
type List struct { head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 // tail *Node // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) // 常规操作 // 初始化List Init(*Node) // 链表遍历 Visit(func) // 判断是否为空 IsEmpty() // 取长度 Length() // 获取第i个结点 Get(int) // 删除第i个结点 Delete(int) // 在最前面插入结点 InsertHead(*Node) // 在第i个结点之后插入结点 Insert(int, *Node) // 反转链表 Reverse() // 双指针相关 // 1、取链表中间结点始第 l.Len()/2向上取整个结点 GetMiddleNode() // 2、取倒数第K个结点 GetTailKthNode(int) }
算法详解
// 初始化:加上头结点 List::Init(node *Node) { head<- new(Node) head.Next<-node } // 链表遍历 List::Visit(vis func(*Node)) { for node <- head to tail { vis(node) } } // 判断是否为空 List::IsEmpty() bool { return head.Next==NULL } // 取长度 List::Length() int { len<-0 for node <- head to tail { len<-len+1 } return len } // 获取第i个结点 List::Get(i int) *Node { cur<-head while(i>0 && cur!=NULL) { i<-i-1 cur<-cur.Next } return cur }
pre最终指向了第i个结点的前一个结点,这样子才方便删除。
删除时直接把Pre.Next指向elem.Next即可。
// 删除第i个结点 如图动画 List::Delete(i int) *Node { pre<-head // 定义pre 最终指向第i个结点的前一个结点 i<-i-1 // 实际实现中用Get(i-1) while(i>0 && pre!=NULL) { i<-i-1 pre<-pre.Next } if pre==NULL || pre.Next==NULL { // i已经超出了范围无效 return NULL } elem <- pre.Next pre.Next<-pre.Next.Next return elem }
1,2 顺序不可调换。 根据贪心原理,我们始终要能够访问到7这个结点,要是调换顺序,7将访问不到了。
// 在最前面插入结点, 即在head后面插入一个元素 List::InsertHead(elem *Node) { elem.Next<-head.Next head.Next<-elem }
查找第i个结点与删除算法类似,区别是i不用减1了,因为这次找的就是第i个结点,之前找的是第i个结点的前一个。插入方法与插入前端位置相同。
// 在第i个结点之后插入结点, 查找第i个结点与删除算法类似 List:: Insert(i int, elem *Node) { pre<-head // 定义pre 最终指向第i个结点,实际实现中用Get(i) while(i>0 && pre!=NULL) { i<-i-1 pre<-pre.Next } if pre==NULL { // i已经超出了范围无效 return } elem.Next<-pre.Next pre.Next<-elem } // 反转链表, 可以采用头插法 List::Reverse() { pre<-head.Next head.Next=NULL while(pre!=NULL) { // 依次遍历 temp<-pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。 pre<-pre.Next InsertHead(temp) } }
中间结点位置 | 链表长度 |
---|---|
1 | 1,2 |
2 | 3,4 |
3 | 5,6 |
4 | 7,8 |
5 | 9,10 |
n | n2-1, n\2 |
// 1、取链表中间结点始第 l.Len()/2向上取整个结点, List::GetMiddleNode() *Node{ if head.Next==NULL { return NULL } first<-head // 每次走一步 second<-head // 每次走2步 /* 从上表可以看出 second走到奇数位时,first就要走一步。 */ while(second!=NULL) { second<-second.Next if second!=NULL { // 只要second能走出一步(奇数位),first就往后走 first<-first.Next second<-second.Next } // 如果是向下取整则是second走2步后first走1步 // if second!=NULL {first<-first.Next} } return first }
利用双指针跟车算法,当last指向nil时,tailKth刚好指向倒数第K个结点。
可以先让last指向第K个结点。然后tailKth指向head。接着同时往前移,直到last=nil。
// 2、取倒数第K个结点,跟车算法 List::GetTailKthNode(k int) *Node{ last<-Get(k) if last==NULL {// length<k return NULL } tailKth<-head while(last!=NULL) { last<-last.Next tailKth<-tailKth.Next } return tailKth }
双向非循环链表
一个结点定义为Node
type Node struct { Val int // 值 Next, Prev *Node }
一个双向链表定义为DuList
type DuList struct { head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 // tail *Node // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) // 常规操作 // 删除第i个结点 Delete(int) // 在最前面插入结点 InsertHead(*Node) }
算法详解
elem为第i个元素,红线为前后指针,由于制作中不会对红线进行制作,所以7,2结点是一直都可以访问到的。图中是先改变7的后续结点,再改变2的前续结点,相反的顺序也是可以的。
注意elem没有后续的情况
// 删除第i个结点 DuList::Delete(i int) *Node { elem<-head while(i>0 && elem!=null) { i<-i-1 elem<-elem.Next } if elem==NULL { // i 太大了 return NULL } elem.Prev.Next<-elem.Next if elem.Next!=NULL { elem.Next.Prev<-elem.Prev } return elem }
这里的关键点在于,2有可能是访问不到的,所以优先把2相关的操作都做完,后面的就没有风险了。
注意要判断head.Next是否为空
// 在最前面插入结点 DuList::InsertHead(*Node) { elem.Next<-head.Next if elem.Next!=NULL { elem.Next.Prev<-elem } head.Next<-elem elem.Prev<-head }
四、具体实现
单链表
package main import "fmt" type Node struct { Val int // 值 Next, Prev *Node } type List struct { head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 // tail *Node // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) } // 常规操作 // 初始化List func (l *List) Init(node *Node) { l.head = &Node{Val: 0, Next: node} } // 数组初始化 func (l *List) InitArr(arr ...int) { l.Init(nil) tail := l.head for _, n := range arr { tail.Next = &Node{Val: n} tail = tail.Next } } // 链表遍历 func (l *List) Visit(vis func(*Node)) { for cur := l.head.Next; cur != nil; cur = cur.Next { vis(cur) } } // 判断是否为空 func (l *List) IsEmpty() bool { return l.head.Next == nil } // 取长度 func (l *List) Length() int { sum := 0 l.Visit(func(node *Node) { sum++ }) return sum } // 获取第i个结点 func (l *List) Get(i int) *Node { cur := l.head for ; i > 0 && cur != nil; i, cur = i-1, cur.Next { } return cur } // 删除第i个结点 func (l *List) Delete(i int) *Node { pre := l.Get(i - 1) if pre == nil || pre.Next == nil { // i已经超出了范围无效 return nil } elem := pre.Next pre.Next = pre.Next.Next return elem } // 在最前面插入结点 func (l *List) InsertHead(elem *Node) { elem.Next = l.head.Next l.head.Next = elem } // 在第i个结点之后插入结点 func (l *List) Insert(i int, elem *Node) { pre := l.Get(i) // 定义pre 最终指向第i个结点,实际实现中用Get(i) if pre == nil { // i已经超出了范围无效 return } elem.Next = pre.Next pre.Next = elem } // 反转链表, 可以采用头插法 func (l *List) Reverse() { pre := l.head.Next l.head.Next = nil for pre != nil { // 依次遍历 temp := pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。 pre = pre.Next l.InsertHead(temp) } } // 双指针相关 // 1、取链表中间结点始第 l.Len()/2向上取整个结点 func (l *List) GetMiddleNode() *Node { if l.head.Next == nil { return nil } first := l.head // 每次走一步 second := l.head // 每次走2步 /* 从上表可以看出 second走到奇数位时,first就要走一步。 */ for second != nil { second = second.Next if second != nil { // 只要second能走出一步(奇数位),first就往后走 first = first.Next second = second.Next } // 如果是向下取整则是second走2步后firt走1步 // if second!=NULL {first<-first.Next} } return first } // 2、取倒数第K个结点 func (l *List) GetTailKthNode(k int) *Node { last := l.Get(k) if last == nil { // length<k return nil } tailKth := l.head for ; last != nil; last, tailKth = last.Next, tailKth.Next { } return tailKth } func main() { arr := []int{2, 3, 4, 5, 6, 7, 7, 8, 8} // InitArr 测试 fmt.Println("InitArr 测试") l := &List{} l.InitArr(arr...) l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println() fmt.Println("InitArr 测试 end") fmt.Println("--------------------------") fmt.Println("Init 测试") l.Init(l.head.Next) l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println() fmt.Println("Init 测试 end") fmt.Println("--------------------------") fmt.Println("IsEmpty 测试") fmt.Println(l.IsEmpty()) l.Init(nil) fmt.Println(l.IsEmpty()) fmt.Println() fmt.Println("IsEmpty 测试 end") fmt.Println("--------------------------") fmt.Println("Length 测试") fmt.Println(l.Length()) for i := 1; i < 10; i++ { l.InsertHead(&Node{Val: i}) fmt.Println(l.Length()) } l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println("\nLength 测试 end") fmt.Println("--------------------------") fmt.Println("Get 测试") fmt.Println(l.Length()) for i := 1; i < 11; i++ { node := l.Get(i) fmt.Printf("%+***", node, node) } fmt.Println("\nGet 测试 end") fmt.Println("--------------------------") fmt.Println("Delete 测试") fmt.Println(l.Length()) node := l.Delete(11) fmt.Printf("%+***", node, node) node = l.Delete(9) fmt.Printf("%+***", node, node) node = l.Delete(8) fmt.Printf("%+***", node, node) node = l.Delete(2) fmt.Printf("%+***", node, node) node = l.Delete(1) fmt.Printf("%+***", node, node) node = l.Delete(5) fmt.Printf("%+***", node, node) fmt.Println("\nDelete 测试 end") fmt.Println("--------------------------") fmt.Println("InsertHead 测试") l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println() l.InsertHead(&Node{Val: 100}) l.InsertHead(&Node{Val: 101}) l.InsertHead(&Node{Val: 99}) l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println("\nInsertHead 测试 end") fmt.Println("--------------------------") fmt.Println("InsertHead 测试") l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println() l.Insert(1, &Node{Val: 1100}) l.Insert(3, &Node{Val: 1101}) l.Insert(2, &Node{Val: 199}) l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println("\nInsertHead 测试 end") fmt.Println("--------------------------") fmt.Println("Reverse 测试") l.Reverse() l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println() l.Reverse() l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println("\nReverse 测试 end") fmt.Println("--------------------------") fmt.Println("GetMiddleNode 测试") l.Init(nil) fmt.Printf("%+***", l.GetMiddleNode(), l.GetMiddleNode()) for i := 1100; i < 1111; i++ { l.InsertHead(&Node{Val: i}) fmt.Printf("%+***", l.GetMiddleNode(), l.GetMiddleNode()) fmt.Printf("%+v\n", l.Get((l.Length()+1)/2)) l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println("len:", l.Length()) } fmt.Println("\nGetMiddleNode 测试 end") fmt.Println("--------------------------") fmt.Println("GetTailKthNode 测试") l.Visit(func(node *Node) { fmt.Printf(", %d", node.Val) }) fmt.Println("len:", l.Length()) node = l.GetTailKthNode(15) fmt.Printf("%+***", node, node) for i := 1; i <= l.Length(); i++ { node := l.GetTailKthNode(i) fmt.Printf("%+***", node, node) } fmt.Println("\nGetTailKthNode 测试 end") fmt.Println("--------------------------") }
双链表
package main import "fmt" type Node struct { Val int // 值 Next, Prev *Node } type DuList struct { head *Node // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 // tail *Node // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) } // 常规操作 // 初始化List func (l *DuList) Init(node *Node) { l.head = &Node{Val: 0, Next: node} if node != nil { node.Prev = l.head } } // 数组初始化 func (l *DuList) InitArr(arr ...int) { l.Init(nil) tail := l.head for _, n := range arr { tail.Next = &Node{Val: n} tail.Next.Prev = tail tail = tail.Next } } // 链表遍历 func (l *DuList) Visit(vis func(*Node)) { for cur := l.head.Next; cur != nil; cur = cur.Next { fmt.Printf("%d, ", cur.Val) if vis != nil { vis(cur) } } fmt.Println() } // 链表遍历 func (l *DuList) VisitReverse() { tail := l.head for cur := l.head.Next; cur != nil; cur = cur.Next { tail = cur fmt.Printf("%d, ", cur.Val) } fmt.Println("reverse") for ;tail != nil && tail != l.head;tail = tail.Prev { fmt.Printf("%d, ", tail.Val) } fmt.Println("") } // 取长度 func (l *DuList) Length() int { sum := 0 l.Visit(func(node *Node) { sum++ }) return sum } // 删除第i个结点 func (l *DuList) Delete(i int) *Node { elem := l.head for ; i > 0 && elem != nil; i, elem = i-1, elem.Next { } if elem == nil { // i 太大了 return nil } elem.Prev.Next = elem.Next if elem.Next!=nil { elem.Next.Prev = elem.Prev } return elem } // 在最前面插入结点 func (l *DuList) InsertHead(elem *Node) { elem.Next = l.head.Next if elem.Next != nil { elem.Next.Prev = elem } l.head.Next = elem elem.Prev = l.head } func main() { arr := []int{2, 3, 4, 5, 6, 7, 7, 8, 8} l := &DuList{} fmt.Println("InitArr 测试") l.InitArr(arr...) l.Visit(nil) l.VisitReverse() fmt.Println() fmt.Println("InitArr 测试 end") fmt.Println("--------==============-------------") fmt.Println("Delete 测试") for ;l.head.Next!=nil; { fmt.Printf("%+v\n",l.Delete(1)) l.VisitReverse() fmt.Println() } fmt.Println("Delete 测试 end") fmt.Println("--------==============-------------") fmt.Println("InsertHead 测试") l.Init(nil) for i:=1;i<11;i++ { l.InsertHead(&Node{Val:i}) l.VisitReverse() fmt.Println() } fmt.Println("InsertHead 测试 end") fmt.Println("--------==============-------------") }
五、牛刀小试
练习1 倒数第K个结点应用
题目链接 https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
题目大意
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1,2], n = 1
输出:[1]
提示:
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
题目解析
可以利用查找倒数第K个方法,找到倒数第K个结点的前一个。然后进行删除。
AC代码
type ListNode struct { Val int // 值 Next *ListNode } type List struct { head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 // tail *Node // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) } // 常规操作 // 初始化List func (l *List) Init(node *ListNode) { l.head = &ListNode{Val: 0, Next: node} } // 链表遍历 func (l *List) Visit(vis func(*ListNode)) { for cur := l.head.Next; cur != nil; cur = cur.Next { vis(cur) } } // 获取第i个结点 func (l *List) Get(i int) *ListNode { cur := l.head for ; i > 0 && cur != nil; i, cur = i-1, cur.Next { } return cur } // 2、取倒数第K个结点 func (l *List) GetTailKthNode(k int) (pre, tailKth *ListNode) { last := l.Get(k) if last == nil { // length<k return nil, nil } tailKth = l.head for ; last != nil; last, tailKth = last.Next, tailKth.Next { pre = tailKth } return pre, tailKth } func removeNthFromEnd(head *ListNode, n int) *ListNode { l := &List{} l.Init(head) pre, tailKth := l.GetTailKthNode(n) pre.Next = tailKth.Next return l.head.Next }
练习2 反转链表
题目大意
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制:
0 <= 节点个数 <= 5000
题目解析
利用头插法反转链表。
AC代码
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ type List struct { head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 // tail *Node // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) } // 常规操作 // 初始化List func (l *List) Init(node *ListNode) { l.head = &ListNode{Val: 0, Next: node} } // 在最前面插入结点 func (l *List) InsertHead(elem *ListNode) { elem.Next = l.head.Next l.head.Next = elem } // 反转链表, 可以采用头插法 func (l *List) Reverse() { pre := l.head.Next l.head.Next = nil for pre != nil { // 依次遍历 temp := pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。 pre = pre.Next l.InsertHead(temp) } } func reverseList(head *ListNode) *ListNode { l := &List{} l.Init(head) l.Reverse() return l.head.Next }
练习3 奇偶链表
题目链接:https://leetcode-cn.com/problems/odd-even-linked-list/
题目大意
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
题目解析
遍历整个链表,将奇数节点收集到一个链表,将偶数结点收集到另一个链表,最后把偶数链表的头放到数链表的尾巴上。
AC代码
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ type List struct { head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 tail *ListNode // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) } // 常规操作 // 初始化List func (l *List) Init(node *ListNode) { l.head = &ListNode{Val: 0, Next: node} l.tail=l.head } // 在最后面添加 func (l *List) AddTail(elem *ListNode) { l.tail.Next = elem l.tail = l.tail.Next l.tail.Next = nil // 删除关联的尾巴 } func oddEvenList(head *ListNode) *ListNode { oddList, evenList := &List{}, &List{} oddList.Init(nil) evenList.Init(nil) for head != nil { temp := head head = head.Next // 添加到奇数链表 oddList.AddTail(temp) if head != nil { // 添加偶数链表 temp, head = head, head.Next evenList.AddTail(temp) } } oddList.tail.Next = evenList.head.Next return oddList.head.Next }
练习4 回文链表
题目链接:https://leetcode-cn.com/problems/palindrome-linked-list/
题目大意
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
题目解析
先将链表分成2半,将后一半链表反转,遍历判断是否相等。
注意奇数个元素的情况
AC代码
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ type List struct { head *ListNode // 头指针,是一个Node, 做一个空指针,实际第一个结点是head.Next开始,head.Next==nil 说明链表为空。 // tail *ListNode // 如果想实现一个队列也可以定义tail 来实现 // length int // 如果经常要访问长度,可以定义length,将长度计算均摊到增删算法中, 做到做到O(1) } // 常规操作 // 初始化List func (l *List) Init(node *ListNode) { l.head = &ListNode{Val: 0, Next: node} } // 在最前面插入结点 func (l *List) InsertHead(elem *ListNode) { elem.Next = l.head.Next l.head.Next = elem } // 反转链表, 可以采用头插法 func (l *List) Reverse() { pre := l.head.Next l.head.Next = nil for pre != nil { // 依次遍历 temp := pre // 这里一定要先复制一份,要不然当前结点插入到新顺序后,就找不到下一结点了。 pre = pre.Next l.InsertHead(temp) } } // 双指针相关 // 1、取链表中间结点始第 l.Len()/2向上取整个结点 func (l *List) GetMiddleNode() *ListNode { if l.head.Next == nil { return nil } first := l.head // 每次走一步 second := l.head // 每次走2步 /* 从上表可以看出 second走到奇数位时,first就要走一步。 */ for second != nil { second = second.Next if second != nil { // 只要second能走出一步(奇数位),first就往后走 first = first.Next second = second.Next } // 如果是向下取整则是second走2步后firt走1步 // if second!=NULL {first<-first.Next} } return first } func isPalindrome(head *ListNode) bool { if head == nil {return true} firstHalf, secondHalf := &List{}, &List{} firstHalf.Init(head) mid := firstHalf.GetMiddleNode() // mid后边属于secondHalf, firstHalf个数 总是大于或等于secondHalf secondHalf.Init(mid.Next) mid.Next=nil // 断开前后2半 secondHalf.Reverse() for fh, sh := firstHalf.head.Next, secondHalf.head.Next; fh!=nil && sh !=nil; fh, sh = fh.Next, sh.Next{ if fh.Val!=sh.Val {return false} } return true }
六、总结
主要内容:
- 在leetcode里链表问题大部分是基础的模拟题,这类题目的难点在于对边界情况的考虑。想要写出准确、高效的代码,需要平时对固定的操作原理及代码了然于心,用到时做到胸有成竹,处变不惊。
- 介绍了链表基础操作和原理。
- 通过练习加强对链表操作的理解,大部分难的题目都是对于基础操作的组合应用。
笔者水平有限,有写得不对或者解释不清楚的地方还望大家指出,我会尽自己最大努力去完善。
下面我精心准备了几个题目,供大家练习参考。干他F.*ing (Fighting?)。
七、实战训练
代码基础训练题
光说不练假把式,学完了怎么也要实操一下吧,快快动用把刚才那2题A了。
- 倒数第K个结点应用 https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
- 反转链表 题目链接 https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/,https://leetcode-cn.com/problems/reverse-linked-list/
- 奇偶链表 题目链接:https://leetcode-cn.com/problems/odd-even-linked-list/
- 双指针取中间值 回文链表 题目链接:https://leetcode-cn.com/problems/palindrome-linked-list/
AK leetcode
leetcode相关题目都在下面了,拿起武器挨个点名呗。
https://leetcode-cn.com/tag/linked-list/problemset/ 链表题目列表
本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。
#字节跳动##内推##校招##实习##社招#