@@ -37,6 +37,22 @@ class Solution:
3737return head
3838```
3939
40+ ``` Python
41+ # Definition for singly-linked list.
42+ # class ListNode:
43+ # def __init__(self, val=0, next=None):
44+ # self.val = val
45+ # self.next = next
46+ class Solution :
47+ def deleteDuplicates (self head : ListNode) -> ListNode:
48+ start= head
49+ while head:
50+ while head.nextand head.val== head.next.val:
51+ head.next= head.next.next
52+ head= head.next
53+ return start
54+ ```
55+
4056###[ remove-duplicates-from-sorted-list-ii] ( https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/ )
4157
4258> 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。
@@ -77,6 +93,25 @@ class Solution:
7793• 删除用一个 Dummy Node 节点辅助（允许头节点可变）
7894• 访问 X.next 、X.value 一定要保证 X != nil
7995
96+ ``` Python
97+ class Solution :
98+ def deleteDuplicates (self head : ListNode) -> ListNode:
99+ dummy= ListNode()
100+ dummy.next= head
101+ pre= dummy
102+ while head:
103+ cur= head.val
104+ if head.nextand cur== head.next.val:
105+ while head.nextand cur== head.next.val:
106+ head= head.next
107+ head= head.next
108+ pre.next= head
109+ else :
110+ pre= head
111+ head= head.next
112+ return dummy.next
113+ ```
114+
80115###[ reverse-linked-list] ( https://leetcode-cn.com/problems/reverse-linked-list/ )
81116
82117> 反转一个单链表。
@@ -115,6 +150,18 @@ class Solution:
115150return rev_next
116151```
117152
153+ ``` Python
154+ class Solution :
155+ def reverseList (self head : ListNode) -> ListNode:
156+ pre= None
157+ while head:
158+ temp= head.next
159+ head.next= pre
160+ pre= head
161+ head= temp
162+ return pre
163+ ```
164+
118165###[ reverse-linked-list-ii] ( https://leetcode-cn.com/problems/reverse-linked-list-ii/ )
119166
120167> 反转从位置 * m* 到 * n* 的链表。请使用一趟扫描完成反转。
@@ -145,6 +192,32 @@ class Solution:
145192return dummy.next
146193```
147194
195+ ``` Python
196+ class Solution :
197+ def reverseBetween (self head : ListNode,left :int ,right :int ) -> ListNode:
198+ if not head.next:
199+ return head
200+ dummy= ListNode()
201+ dummy.next= head
202+ pre= dummy
203+ count= 1
204+ while count< left:
205+ pre= head
206+ head= head.next
207+ count+= 1
208+ cur= pre
209+ start= head
210+ while count<= right:
211+ temp= head.next
212+ head.next= cur
213+ cur= head
214+ head= temp
215+ count+= 1
216+ pre.next= cur
217+ start.next= head
218+ return dummy.next
219+ ```
220+
148221###[ merge-two-sorted-lists] ( https://leetcode-cn.com/problems/merge-two-sorted-lists/ )
149222
150223> 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
@@ -173,6 +246,26 @@ class Solution:
173246return dummy.next
174247```
175248
249+ ``` Python
250+ class Solution :
251+ def mergeTwoLists (self l1 : ListNode,l2 : ListNode) -> ListNode:
252+ dummy= ListNode()
253+ head= dummy
254+ while l1and l2:
255+ if l1.val< l2.val:
256+ head.next= l1
257+ l1= l1.next
258+ else :
259+ head.next= l2
260+ l2= l2.next
261+ head= head.next
262+ if l1:
263+ head.next= l1
264+ if l2:
265+ head.next= l2
266+ return dummy.next
267+ ```
268+
176269###[ partition-list] ( https://leetcode-cn.com/problems/partition-list/ )
177270
178271> 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 * x* 的节点都在大于或等于 * x* 的节点之前。
@@ -204,6 +297,25 @@ class Solution:
204297
205298> 当头节点不确定的时候，使用哑巴节点
206299
300+ ``` Python
301+ class Solution :
302+ def partition (self head : ListNode,x :int ) -> ListNode:
303+ if not heador not head.next:
304+ return head
305+ s_head= s= ListNode(next = head)
306+ l_head= l= ListNode()
307+ while s.next:
308+ if s.next.val< x:
309+ s= s.next
310+ else :
311+ l.next= s.next
312+ s.next= s.next.next
313+ l= l.next
314+ l.next= None
315+ s.next= l_head.next
316+ return s_head.next
317+ ```
318+
207319###[ sort-list] ( https://leetcode-cn.com/problems/sort-list/ )
208320
209321> 在 * O* (* n* log * n* ) 时间复杂度和常数级空间复杂度下，对链表进行排序。
@@ -257,6 +369,40 @@ class Solution:
257369- 递归 mergeSort 需要断开中间节点
258370- 递归返回条件为 head 为 nil 或者 head.Next 为 nil
259371
372+ ``` Python
373+ class Solution :
374+ def middle (self head ):
375+ slow, fast= head, head.next
376+ while fastand fast.next:
377+ slow= slow.next
378+ fast= fast.next.next
379+ return slow
380+
381+ def merge (self l1 ,l2 ):
382+ head= l= ListNode()
383+ while l1and l2:
384+ if l1.val< l2.val:
385+ l.next= l1
386+ l1= l1.next
387+ else :
388+ l.next= l2
389+ l2= l2.next
390+ l= l.next
391+ if l1:
392+ l.next= l1
393+ if l2:
394+ l.next= l2
395+ return head.next
396+
397+ def sortList (self head : ListNode) -> ListNode:
398+ if not heador not head.next:
399+ return head
400+ mid= self .middle(head)
401+ sec= mid.next
402+ mid.next= None
403+ return self .merge(self .sortList(head),self .sortList(sec))
404+ ```
405+
260406###[ reorder-list] ( https://leetcode-cn.com/problems/reorder-list/ )
261407
262408> 给定一个单链表 * L* ：* L* →* L* →…→* L\_\_ n* →* L*
@@ -303,6 +449,40 @@ class Solution:
303449return
304450```
305451
452+ ``` Python
453+ class Solution :
454+ def reorderList (self head : ListNode) ->None :
455+ """
456+ Do not return anything, modify head in-place instead.
457+ """
458+ if not heador not head.next:
459+ return head
460+
461+ slow= l1= head
462+ fast= head.next
463+ while fastand fast.next:
464+ fast= fast.next.next
465+ slow= slow.next
466+ cur= slow.next
467+ pre= None
468+ slow.next= None
469+
470+ while cur:
471+ temp= cur.next
472+ cur.next= pre
473+ pre= cur
474+ cur= temp
475+
476+ while l1and pre:
477+ tpre= pre.next
478+ pre.next= l1.next
479+ l1.next= pre
480+ l1= l1.next.next
481+ pre= tpre
482+
483+ return head
484+ ```
485+
306486###[ linked-list-cycle] ( https://leetcode-cn.com/problems/linked-list-cycle/ )
307487
308488> 给定一个链表，判断链表中是否有环。
@@ -326,6 +506,19 @@ class Solution:
326506return False
327507```
328508
509+ ``` Python
510+ class Solution :
511+ def hasCycle (self head : ListNode) ->bool :
512+ slow= head
513+ fast= head
514+ while fastand fast.next:
515+ fast= fast.next.next
516+ slow= slow.next
517+ if fast== slow:
518+ return True
519+ return False
520+ ```
521+
329522###[ linked-list-cycle-ii] ( https://leetcode-cn.com/problems/linked-list-cycle-ii/ )
330523
331524> 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 ` null ` 。
@@ -365,6 +558,22 @@ class Solution:
365558- fast 如果初始化为 head.Next 则中点在 slow.Next
366559- fast 初始化为 head,则中点在 slow
367560
561+ ``` Python
562+ class Solution :
563+ def detectCycle (self head : ListNode) -> ListNode:
564+ fast= slow= head
565+ while fastand fast.next:
566+ fast= fast.next.next
567+ slow= slow.next
568+ if fast== slow:
569+ slow= head
570+ while fast!= slow:
571+ fast= fast.next
572+ slow= slow.next
573+ return slow
574+ return None
575+ ```
576+
368577###[ palindrome-linked-list] ( https://leetcode-cn.com/problems/palindrome-linked-list/ )
369578
370579> 请判断一个链表是否为回文链表。
@@ -393,6 +602,29 @@ class Solution:
393602return True
394603```
395604
605+ ``` Python
606+ class Solution :
607+ def isPalindrome (self head : ListNode) ->bool :
608+ slow= head
609+ fast= head
610+ while fastand fast.next:
611+ fast= fast.next.next
612+ slow= slow.next
613+ pre= None
614+ while slow:
615+ temp= slow.next
616+ slow.next= pre
617+ pre= slow
618+ slow= temp
619+ while pre:
620+ if head.val== pre.val:
621+ pre= pre.next
622+ head= head.next
623+ else :
624+ return False
625+ return True
626+ ```
627+
396628###[ copy-list-with-random-pointer] ( https://leetcode-cn.com/problems/copy-list-with-random-pointer/ )
397629
398630> 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
@@ -461,6 +693,25 @@ class Solution:
461693return new
462694```
463695
696+ ``` Python
697+ class Solution :
698+ def copyRandomList (self head :' Node' ' Node'
699+ if not head:
700+ return None
701+ copy= {}
702+ m= n= head
703+ while m:
704+ copy[m]= Node(m.val)
705+ m= m.next
706+ while n:
707+ if n.next:
708+ copy[n].next= copy[n.next]
709+ if n.random:
710+ copy[n].random= copy[n.random]
711+ n= n.next
712+ return copy[head]
713+ ```
714+
464715##总结
465716
466717链表必须要掌握的一些点，通过下面练习题，基本大部分的链表类的题目都是手到擒来~