1、链表的中间节点
1）初始化结构不会写啊。。。
2）class ListNode:
def __init__(self,x):
self.val=x
self.next=None
l1=ListNode(1)
l2=l1
for i in range(2,7):
l1.next=ListNode(i)
l1=l1.next
fast=l2
slow=l2
while fast:
if fast.next:
fast=fast.next.next
slow=slow.next
else:
fast=fast.next
print(slow.val)
2、链表每k个一组反转
核心思想：头插法
每一次把当前节点插到最前面
tmp=cur.next
cur.next=tmp.next
tmp.next=pre.next
pre.next=tmp
1）参考思路：
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=117&&tqId=37746&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
2）核心代码
3、链表的公共节点
1）哈希存储其中一个链表
p1=pHead1
p2=pHead2
dict1={}
while p1:
if p1 not in dict1:
dict1[p1]=1
else:
continue
p1=p1.next
while p2:
if p2 in dict1:
return p2
p2=p2.next
return
2）双指针
p1=pHead1
p2=pHead2
while (p1!=p2):
if p1:
p1=p1.next
else:
p1=pHead2
if p2:
p2=p2.next
else:
p2=pHead1
return p2
4、链表相加
牛客网：https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b?tpId=117&&tqId=37814&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
两个链表生成相加链表
描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例1
输入：[9,3,7],[6,3]
返回值：{1,0,0,0}
核心思路：
明确相加之后进几余几
核心代码如下：
def addInList(self , head1 , head2 ):
# write code here
def reverse(head):
pre=None
cur=head
while cur:
tmp=cur.next
cur.next=pre
pre=cur
cur=tmp
return pre
p1=reverse(head1)
p2=reverse(head2)
node=ListNode(0)
res=node
restay=0
while p1 or p2:
if not p1:
p1=ListNode(0)
if not p2:
p2=ListNode(0)
tmp=p1.val+p2.val
tmp1=(restay+tmp)%10
restay=(restay+tmp)//10
node.next=ListNode(tmp1)
node=node.next
p1=p1.next
p2=p2.next
if restay!=0:
node.next=ListNode(restay)
return reverse(res.next)
5、合并K个有序链表
1）利用堆结构实现最小堆，进而对K个链表排序
首先，对链表首元素，加入堆中
pop出最小元素，后判断下一节点，再调整最小堆
核心代码如下：
import heapq
d = ListNode(0)
p = d
head = []
for i in range(len(lists)):
if lists[i] :
heapq.heappush(head, (lists[i].val, i))
lists[i] = lists[i].next
while head:
val, idx = heapq.heappop(head)
p.next = ListNode(val)
p = p.next
if lists[idx]:
heapq.heappush(head, (lists[idx].val, idx))
lists[idx] = lists[idx].next
return d.next
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6?tpId=117&&tqId=37747&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
2）递归调用
先实现合并两个有序链表，在进行递归实现合并所有链表
核心代码如下：
def merge(l1,l2):
l=ListNode(0)
pre=l
whilel1 and l2:
ifl1.val<=l2.val:
pre.next=l1
l1=l1.next
else:
pre.next=l2
l2=l2.next
pre=pre.next
ifl1:
pre.next=l1
ifl2:
pre.next=l2
returnl.next
ifnot lists:
returnNone
iflen(lists)<=1:
returnlists[0]
iflen(lists)==2:
returnmerge(lists[0],lists[1])
k2=len(lists)//2
left=self.mergeKLists(lists[:k2])
right=self.mergeKLists(lists[k2:])
returnself.mergeKLists([left,right])
6、链表环的问题
1）链表是否有环
哈希表/快慢指针
if not head or not head.next:
return False
slow=head
fast=head.next
while fast!=slow:
if not fast or not fast.next:
return False
slow=slow.next
fast=fast.next.next
return True
https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=191&&tqId=36289&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
2）环的入口节点
哈希表/快慢指针
fast, slow = pHead, pHead
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = pHead
while fast != slow:
fast, slow = fast.next, slow.next
return fast
参考题解：
环形链表 II（双指针法，清晰图解）
https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=191&&tqId=36292&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
7、链表重排
核心思路：中间节点+反转链表+链表合并
def reorderList(self , head ):
# write code here
def reverse(l):
pre=None
p1=l
while p1:
tmp=p1.next
p1.next=pre
pre=p1
p1=tmp
return pre
def mergeList(l1: ListNode, l2: ListNode):
while l1 and l2:
l1_tmp = l1.next
l2_tmp = l2.next
l1.next = l2
l1 = l1_tmp
l2.next = l1
l2 = l2_tmp
if not head or not head.next:
return head
fast=head
slow=head
while fast.next and fast.next.next:
fast=fast.next.next
slow=slow.next
mid=slow
l1 = head
l2 = mid.next
mid.next = None
l2 = reverse(l2)
return mergeList(l1,l2)
https://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b?tpId=191&&tqId=36654&rp=1&ru=/activity/oj&qru=/ta/job-code-high-algorithm/question-ranking
https://leetcode-cn.com/problems/reorder-list/solution/zhong-pai-lian-biao-by-leetcode-solution/
