从尾到头打印链表
#递归
def reversePrint(self, head: ListNode) -> List[int]:
if not head:
return []
return self.reversePrint(head.next) + [head.val]#迭代
def reversePrint(self, head: ListNode) -> List[int]:
res = []
while head:
res.insert(0,head.val)
head = head.next
return res翻转链表
# 迭代，双指针，交换顺序很重要！！！
def reverseList(self, head: ListNode) -> ListNode:
cur = head
pre = None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre链表倒数第k个节点
# 双指针，第一个指针先走k步
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
cur = head
pre = head
while k:
cur = cur.next
k -= 1
while cur and pre:
cur = cur.next
pre = pre.next
return pre合并两个链表
#方法一：迭代
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
res = ListNode(0)
p = res
while l1 and l2:
if l1.val < l2.val:
p.next = l1
l1 = l1.next
else:
p.next = l2
l2 = l2.next
p = p.next
while l1:
p.next = l1
l1 = l1.next
p = p.next
while l2:
p.next = l2
l2 = l2.next
p = p.next
return res.next#方法二，递归
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: # 递归停止条件
return l2
if not l2: # 递归停止条件
return l1
pre = None
if l1.val <= l2.val:
pre = l1
pre.next = self.mergeTwoLists(l1.next, l2)
else:
pre = l2
pre.next = self.mergeTwoLists(l1,l2.next)
return pre复杂链表的复制
#方法一：哈希表
#与普通链表复制不同的是，在复制某个节点时，这个节点的random指向可能还没有被创建，因此可以先用一个哈希表创建所有节点，第二次遍历
#改变每个节点的next和random指向即可
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return head
d = {}
cur = head
while cur:
d[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
d[cur].next = d.get(cur.next)
d[cur].random = d.get(cur.random)
cur = cur.next
return d[head]#方法二
#在每个节点后面插入一个相同的新节点，第二次遍历修改random指向
#最后一次遍历，每次走两步，得到复制链表
if not head:
return head
cur = head
while cur:
copy = Node(cur.val)
copy.next = cur.next
cur.next = copy
cur = cur.next.next
cur = head
while cur:
if cur.random != None:
cur.next.random = cur.random.next
cur = cur.next.next
res = head.next
cur = head
while cur and cur.next:
temp = cur.next
cur.next = temp.next
cur = temp
return res两个链表的第一个公共节点
#方法一
#两个指针，指向两个链表，走到头之后指向另外一个，如果有交点，两个指针肯定会相遇
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
cur1, cur2 = headA, headB
while cur1 != cur2:
cur1 = cur1.next if cur1 else headB
cur2 = cur2.next if cur2 else headA
return cur1#方法二
#计算链表长度，让长的链表先走la-lb步，接着两个一起走
#相同则返回
def getLen(self,head):
cur = head
l = 0
while cur:
cur = cur.next
l += 1
return l
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
# if headB == headA:
# return headA
la = self.getLen(headA)
lb = self.getLen(headB)
cura = headA
curb = headB
d = abs(la-lb)
ret = 0
if la > lb:
while d:
cura = cura.next
d -= 1
else:
while d:
curb = curb.next
d -= 1
while cura and curb:
if cura == curb:
return cura
cura = cura.next
curb = curb.next
return 链表中环的入口
#快慢指针判断是否有环
#若存在环，慢指针和一个新的从head开始遍历的指针的第一个相同指向就是环的入口
def detectCycle(self, head: ListNode) -> ListNode:
if not head:
return
p1 = head
p2 = head
hascycle = False
while p2.next and p2.next.next:
p1 = p1.next
p2 = p2.next.next
if p1 == p2:
hascycle = True
break
if hascycle:
q = head
while q != p1:
p1 = p1.next
q = q.next
return q
return删除链表重复节点
#方法一：递归
def deleteDuplicates(self, head: ListNode) -> ListNode:
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#方法二：迭代
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
pre = head
cur = head.next
while cur:
if cur.val == pre.val:
pre.next = cur.next
else:
pre = cur
cur = cur.next
return head两两交换链表中的相邻节点
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
nextNode = head.next
head.next = self.swapPairs(nextNode.next)
nextNode.next = head
return nextNode合并K个链表
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import heapq
dummy = ListNode(0)
p = dummy
head = []
# k个指针指向k个链表
for i in range(len(lists)):
if lists[i]:
heapq.heappush(head,(lists[i].val,i))
lists[i] = lists[i].next
while head:
#每次pop出最小的一个元素
val, idx = 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 dummy.next翻转固定范围的链表
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
dummy = ListNode(0)
dummy.next = head
pre = dummy
m = left
n = right
for x in range(1,m):
pre = pre.next
head = pre.next
for x in range(m, n):
nex = head.next
head.next = nex.next
nex.next = pre.next
pre.next = nex
return dummy.next