【Code Practice】
目录
1.10 查找链表的中间节点（如果中间有两个节点，返回第二个）
1.12 判断是否是回文链表（时间复杂度O(n)和空间复杂度都是O(1)）
1.19 重排链表（1-2-3-4-5 》 1-5-2-4-3）
1 链表类
1.1 反转链表
增加两个指针，pre每次保存前一个，next保存后一个（防止断开），反转顺序，phead.next->pre，然后pre和phead依次后移（pre=phead, phead=next），最后终止条件是pHead=None，返回前一个节点pre
def ReverseList(self, pHead):
# write code here
if not pHead:
return None
pre=None
pnext=None
while pHead:
pnext=pHead.next
pHead.next=pre
pre=pHead
pHead=pnext
return pre #此时pHead=None.返回的是前一个节点
#递归方法：
"""
if not head or not head.next:
return head
p=self.reverseList(head.next)
head.next.next=head
head.next=None
return p
"""
#头插法（依次将后面节点移到头节点）
if not head or not head.next:
return head
dummy=ListNode(-1)
dummy.next=head
pre=dummy
p=dummy.next
while p.next:
temp=p.next
p.next=temp.next
temp.next=pre.next
pre.next=temp
return dummy.next1.2 从尾到头打印链表
思路一：从头到尾依次打印并保存，逆序返回
思路二：递归实现，每次都先递归到下一个节点，当前值最后保存，则保存的结果就是从最后一个节点向前的顺序
递归时，两个关键因素：终止条件，递归过程的语句顺序（此题中，先依次调用本函数，再添加元素，注意语句顺序）
#method 1:
def printListFromTailToHead(self, listNode):
# write code here
a=[]
while listNode:
a.append(listNode.val)
listNode=listNode.next
return a[::-1]
#method 2:
def __init__(self):
self.res=[]
def printListFromTailToHead(self, listNode):
if listNode:
self.printListFromTailToHead(listNode.next)
self.res.append(listNode.val)
return self.res
#or:
def printListFromTailToHead(self, listNode):
if not listNode:
return []
return self.printListFromTailToHead(listNode.next)+[listNode.val]1.3 查找链表中倒数第k个节点
思路一：一次遍历找到总长度，然后再遍历len-k+1步（时间复杂度较高）
思路二：快慢指针方法（两个指针，快的先走，慢的相隔k-1步再走，当快的走到尾时，慢的刚好在倒数第k个，返回慢的）
考虑特殊情况：空链表、k为0、链表长度小于k
快慢指针还可解决：查找链表中间节点（快的一次走两步，慢的一次走一步，快的到尾时，返回慢的）
def FindKthToTail(self, head, k):
# write code here
if not head or k==0:
return None
pbehind=head
for i in range(k-1):
if head.next: #注意此处判断条件
head=head.next
else: #考虑长度小于k的情况
return None
while head.next: #注意此处判断条件
head=head.next
pbehind=pbehind.next
return pbehind1.4 合并两个递增的有序链表
思路一：非递归，新建一个列表，并记录表头。在都不为空的情况下，顺次比较两个链表的表头，每次取出较小的为新链表的下一个节点，然后较小的节点后移。每比较一次，新链表的记录都后移一次（否则只会在表头操作）。遍历结束后，如果有非空的，则直接添加。最后返回新链表的记录表头。
思路二：递归
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
#递归方法：
if not pHead1:
return pHead2
if not pHead2:
return pHead1
if pHead1.val<pHead2.val:
merge=pHead1
merge.next=self.Merge(pHead1.next,pHead2)
else:
merge=pHead2
merge.next=self.Merge(pHead1,pHead2.next)
return merge
"""
非递归方法：
pnew=ListNode(-1)#任意指定一个头为-1的链表
res=pnew #保存该链表的头，因为后面pnew会一直后移，需要记录表头位置
while pHead1 and pHead2:
if pHead1.val<pHead2.val:
pnew.next=pHead1
pHead1=pHead1.next
else:
pnew.next=pHead2
pHead2=pHead2.next
pnew=pnew.next #每次都要后移当前节点，否则会一直在第一个-1节点
if pHead1:
pnew.next=pHead1
if pHead2:
pnew.next=pHead2
return res.next #因为头节点是-1，从下一个开始返回
"""1.5 复杂链表的复制（带一个random）
带random，可能在前面也可能在后面，不能直接复制。三步：
每个节点后面都插入一个该节点的复制；将复制节点的random链接（原节点的random.next）；拆分，返回所有复制节点
def Clone(self, pHead):
# write code here
#递归方法：
if not pHead:
return None
clonehead=RandomListNode(pHead.label)
clonehead.random=pHead.random
clonehead.next=self.Clone(pHead.next)
return clonehead
"""
非递归
#1 复制原链表
pclone=pHead#避免破坏原链表表头
while pclone:
copy=RandomListNode(pclone.label)
pnext=pclone.next
pclone.next=copy
copy.next=pnext
pclone=pnext
#2 复制random
dummy=pHead
while dummy:
clone=dummy.next
if dummy.random:
clone.random=dummy.random.next
dummy=clone.next
#3 返回复制链表（偶数项）
dummy=pHead
copyNode=pHead.next
while dummy:
copynode=dummy.next
dummynext=copynode.next
if dummynext:
copynode.next=dummynext.next
else:
copynode.next=None
dummy=dummynext
return copyNode
"""1.6 两个链表的第一个公共节点
思路一：先遍历得到两个长度差step，然后长链表先走step，然后两个一起走并比较是否相等，返回第一个相等的节点
思路二：分别遍历并用两个栈分布存储，然后从栈顶开始一次pop，返回最后一个相等的点
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
#method 1
#先分别遍历得到长度
length1,length2=0,0
pHead11=pHead1
pHead22=pHead2
while pHead11:
length1+=1
pHead11=pHead11.next
while pHead22:
length2+=1
pHead22=pHead22.next
if length2>=length1:
longhead=pHead2
shorthead=pHead1
else:
longhead=pHead1
shorthead=pHead2
step=abs(length2-length1)
#长链表先走，直到两个长度相等，然后同时走，
for i in range(step):
longhead=longhead.next
while longhead and shorthead:
if longhead==shorthead:
return longhead
longhead=longhead.next
shorthead=shorthead.next
"""
method 2
stack1=[]
stack2=[]
while pHead1:
stack1.append(pHead1)
pHead1=pHead1.next
while pHead2:
stack2.append(pHead2)
pHead2=pHead2.next
temp=None
while stack1 and stack2 and stack1[-1]==stack2[-1]:
temp=stack1[-1] #存储每一对相等的点
stack1.pop()
stack2.pop()
return temp
"""1.7 链表环的入口节点
快慢指针，快一次走两步，慢一次走一步，直到第一次相遇；
假设环有n个节点，第一次相遇时，慢的走了a，快的走了2a，则有a+n=2a ,a=n,即慢的走了n步；
此时再让快的回到头，两个一起走每次都为一步，设x为头距入口的距离，y是入口距慢的距离，x+y=n, 所以当快走x步到达入口时，慢的走了x=n-y步,即一周又退回到入口处，两个刚好相遇
#判断是否有环：快慢指针，如果相遇，则有环
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
f,s=head,head
while f and f.next:
f=f.next.next
s=s.next
if f==s:
return True
return False
#查找环的入口
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead or not pHead.next or not pHead.next.next:
return None
slow=pHead.next
fast=pHead.next.next
while fast != slow:
if not fast.next or not fast.next.next: #要判断，如果有None则说明没有环
return None
slow=slow.next
fast=fast.next.next
#slow刚好走了n步（n:环的节点个数）
# fast退回头结点，两个同时走，每次一步，直到再相遇
fast=pHead
while fast!=slow:
fast=fast.next
slow=slow.next
return fast1.8 删除链表中的重复节点（1-2-2-3—>1-3）
对于链表操作，主要是确定next，建立一个链表res=ListNode(-1)，然后定义指向链表头的指针pre=res，通过操作pre指定next，指针pre依次后移，最后返回建立起res完整链表，最后返回的是res（因为pre一直在变，是操作指针）
#递归方法
#method 1
def deleteDuplication(self, pHead):
# write code here
if pHead==None or pHead.next==None:
return pHead
if pHead.val==pHead.next.val:
temp=pHead.next
while temp!=None and temp.val==pHead.val:
temp=temp.next
return self.deleteDuplication(temp)
else:
temp=pHead.next
pHead.next=self.deleteDuplication(temp)
return pHead
"""
# 非递归方法
if not head or not head.next:
return head
dummy=ListNode(-1)
dummy.next=head
p=dummy
while head and head.next:
if head.next.val==head.val:
val=head.val
while head and head.val==val:
head=head.next
p.next=head #只记录，不后移
else:
p=head #只有不重复时候，才会后移并记录
head=head.next
if head:p.next=head
return dummy.next
"""
#重复节点，保留一个 1-1-2-3-3（1-2-3）
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
Head=ListNode(0)
p=Head
while head !=None and head.next!=None:
if head.val==head.next.val:
p.next=head #甭管重复与否，先记录
temp=head.val
while head and head.val==temp:
head=head.next
else:
p.next=head
head=head.next
p=p.next #每次都会后移
p.next=head
return Head.next
"""
#递归方法
if not head or not head.next:
return head
head.next=self.deleteDuplicates(head.next)
if head.val==head.next.val:
head=head.next
return head
"""1.9 删除链表节点O(1)
将该节点的下一个节点值复制到该节点上，然后跳过下一个节点，指向node.next.next
def deleteNode(self,phead, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
#若是尾节点，需要从头遍历
if node.next==None:
while phead.next!=node:
phead=phead.next
phead.next=None
else:#非尾节点
node.val=node.next.val #复制下个节点值到当前节点
node.next=node.next.next #跳过下个节点1.10 查找链表的中间节点（如果中间有两个节点，返回第二个）
快慢指针。重点是判断条件。
def middleNode(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
fast=head
slow=head
#当下一个非空，下下一个空，也要再走一步，slow就是第二个中间节点了
while fast!=None and fast.next!=None:
fast=fast.next.next
slow=slow.next
return slow1.11 删除指定值的节点
遍历，如果非val，则加入p，head后移，p也后移，否则head后移不加入p。
特殊情况：（1,2,5,6）val=6的情况，最后几个元素是val值，则p加入的最后一个元素是5，但是5的next还是6，所以结果还是1256，所以遍历结束后，指定p.next为head（此时head为空）或None
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
H=ListNode(0)
p=H
while head:
if head.val!=val:
p.next=head
head=head.next
p=p.next
else:
head=head.next
p.next=head #特殊情况，最后几个元素是val
return H.next1.12 判断是否是回文链表（时间复杂度O(n)和空间复杂度都是O(1)）
回文：翻转后和原来一样。空间复杂度是O（1），说明不能建立新的复制链表了，只能原地操作，唯有原地反转了。如果都反转则无法比较了。所以，只反转后半部分，然后和前半部分进行逐一比较。快慢指针找到中间节点->反转后半部分->前后比较
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast,slow=head,head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
mid=slow
pre=None
while mid:
nex=mid.next
mid.next=pre
pre=mid
mid=nex
#pre是后半部分反转后的头节点
while pre:
if pre.val!=head.val: #比较的值是否一样，记得加val！！！
return False
pre=pre.next
head=head.next
return True1.13 链表排序
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
思路一：先遍历一遍并用数组记录链表的所有值，对数组排序，再遍历一遍以数组值将每个节点重新重新赋值
思路二：归并算法：快慢指针，查找中间节点；合并两个子链表。
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
"""
#归并法：快慢指针每次找到中间节点，合并两个子链表
if not head or not head.next:
return head
fast,slow=head,head
pre=None
while fast and fast.next:
pre=slow #保存最终中间节点的前一个值，并赋值None，实现分割
slow=slow.next
fast=fast.next.next
pre.next=None #将head实现分割
left=self.sortList(head)
right=self.sortList(slow)
return self.merge(left,right)
def merge(self,left,right):
if not left:
return right
if not right:
return left
if left.val<right.val:
res=left
res.next=self.merge(left.next,right)
else:
res=right
res.next=self.merge(left,right.next)
return res
"""
#用链表存储所以节点值，然后排序，并给链表从头重新赋值，但是空间复杂度是O（n）
res=[]
q=head
while q:
res.append(q.val)
q=q.next
res.sort()
q=head
leng=len(res)
for i in range(leng):
q.val=res[i]
q=q.next
return head1.14 链表插入排序
新建链表，指向head，每次比较时，先取出当前节点，然后从头遍历新链表找到插入的位置，然后将当前节点插入到该位置，当前点继续后移。
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
"""
if not head or not head.next:
return head
dummy=ListNode(-1)
q=head
while q:
temp=q.next
pre=dummy
while pre.next and pre.next.val<q.val:
pre=pre.next
q.next=pre.next
pre.next=q
q=temp
return dummy.next
"""
#不额外开辟新的链表空间，直接指向当前链表
if head is None or head.next is None:
return head
dummy=ListNode(0)
cur=dummy.next=head
while cur.next:
if cur.val>cur.next.val:
pre=dummy
while pre.next.val<cur.next.val:
pre=pre.next
m=cur.next
cur.next=m.next
m.next=pre.next
pre.next=m
else:
cur=cur.next
return dummy.next1.15 删除倒数第n个节点
考察求倒数第n+1个节点
思路一：两次遍历：先遍历一遍，得到总长度，然后从头遍历直接找到倒数第n+1的节点，删除
思路二：快慢指针，先找到倒数第n个节点（fast和slow相隔n-1步），并记录倒数第n+1节点，然后删除；或者fast和slow相隔n步，则可以直接找到倒数第n+1个节点）
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
#fast和slow相隔n步，直接找到倒数第n+1个节点（注意特殊情况
#n有可能是头节点,此时fast刚好是None）
if not head:
return None
fast,slow=head,head
#假设n有效，不判断n是否超出长度
#fast先走n-1步，找到倒数第n个节点；走n步，
#找到倒数n节点的前一个节点
for i in range(n):
fast=fast.next
if i<n-1 and fast==None: #判断n是否有效
return None
if fast==None: #刚好是要删除头结点
head=head.next
return head
else: #找到倒数第n+1个节点
while fast.next:
fast=fast.next
slow=slow.next
slow.next=slow.next.next
return head
"""
fast和slow相隔n-1步，直接找到slow是倒数第n个节点，此时要记录倒数第n+1节点
if not head:
return None
fast,slow=head,head
for i in range(n-1):
fast=fast.next
if fast==None:
return None
dummy=ListNode(-1)
dummy.next=head
q=dummy
#slow刚好找到倒数第n个节点
#q比slow还慢一步，刚好是slow前面的节点
while fast.next:
fast=fast.next
q=q.next
slow=slow.next
temp=slow
q.next=temp.next
return dummy.next
"""1.16 两两交换链表的节点
记录当前节点，下一个节点，两个反转，然后后移。注意第一个节点要和第四个节点连接（当第三个是非空时）第三个为空时则和第三个节点相连。否则会断开
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
pre=head
p=pre.next
head=head.next
while p and pre:
temp=p.next
p.next=pre
if not temp:
pre.next=temp
return head
#注意，第一个和第四个连接，只有第四个是空时和第三个连接
pre.next=temp if temp.next== None else temp.next
pre=temp
p=temp.next
return head
"""
#递归
if not head or not head.next:
return head
nex=head.next
head.next=self.swapPairs(nex.next)
nex.next=head
return nex
"""1.17 奇偶链表（index，偶数连偶数，接奇数连奇数）
分别定义偶数头节点和奇数头节点，依次后移，最后偶数最后一个节点接奇数的头结点
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
dummy=head
dummy_odd=head.next
peven=dummy
podd=dummy_odd
while podd and podd.next:
peven.next=podd.next
peven=peven.next
podd.next=peven.next
podd=podd.next
if podd: #偶数个节点的情况，需要将最后一个偶数节点的next指定为空
podd.next=None
peven.next=dummy_odd #最后一个偶数节点，接奇数头结点
return dummy1.18 反转链表II（反转第m-n的节点）
思路一：普通原地反转，找到并记录几个关键节点方便后续连接（第m,m-1,n,n+1）
思路二：头插法反转更容易理解。新建头结点，向后遍历，依次将p.next插入至头结点的后面。
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
#头插法，简单明了：
if not head or not head.next:
return head
dummy=ListNode(-1)
dummy.next=head
p=dummy
#先移动m步，找到头结点pre：
for i in range(m):
pre=p
p=p.next
#每次移动，都插入到头结点后面
for j in range(n-m): #总是通不过，发现竟然写成了m-n
temp=p.next
p.next=temp.next
temp.next=pre.next
pre.next=temp
return pre
"""
#普通做法，反转第m-n的链表，再拼接
dummy=ListNode(-1)
dummy.next=head
pm=dummy
for i in range(m):
front=pm #记录第n-1个节点
pm=pm.next
pre=pm #记录第n个节点
pnewpre=None
for j in range(n-m+1): #要多走一步，pm指向第n+1个节点
nex=pm.next
pm.next=pnewpre
pnewpre=pm
pm=nex
front.next=pnewpre
pre.next=pm
return dummy.next
"""1.19 重排链表（1-2-3-4-5 》 1-5-2-4-3）
思路：三步走，快慢指针找到中间节点，反转后半部分，前后两部分合并
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return head
#1 快慢指针，找到中间节点
fast=slow=head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
#2 将后半部分逆序，头插法
head_back=ListNode(-1)
head_back.next=slow.next #后半部分的头结点,保证后半部分小于前半部分，方便合并
p=head_back.next
pre=head_back
while p and p.next:
temp=p.next
p.next=temp.next
temp.next=pre.next
pre.next=temp
#后半部分是head_back.next，已经逆序
slow.next=None #将前半部分封死
#3 两段合并
#1-2-3-Null
#4-5-null
#1-2-3-null
#4-null
head2=head_back.next
head1=head
while head2:
temp2=head2.next
temp1=head1.next
head1.next=head2
head2.next=temp1
head2=temp2
head1=temp1