1、创建链表
class ListNode: def __init__(self,x): self.val = x self.next = None class MyLinkedList: def __init__(self): self.size = 0 self.head = ListNode(0) def get(self,index): if index<0 or index >=self.size: return -1 curr = self.head for _ in range(index+1): curr = curr.next return curr.val def addAtHead(self,val): self.addAtIndex(0,val) def addAtTail(self,val): self.addAtIndex(self.size,val) def addAtIndex(self,index,val): if index > self.size: return if index < 0: index = 0 self.size += 1 pred = self.head for _ in range(index+1): pred = pred.next to_add = ListNode(val) to_add.next = pred.next pred.next = to_add def deteleAAtIndex(self,index): if index < 0 or index >= self.size: return self.size -= 1 pred = self.head for _ in range(index+1): pred = pred.next pred.next = pred.next.next
使用双链表进行增删查找：
class ListNode: def __init__(self,x): self.val = x self.next = None self.prev = None class MyLinkedList: def __init__(self): self.size = 0 self.head = ListNode(0) self.tail = ListNode(0) self.head.next = self.tail self.tail.prev = self.head def get(self,index): if index < 0 or index >=self.size: return -1 if index + 1 < self.size - index: curr = self.head for _ in range(index+1): curr = curr.next else: curr =self.tail for _ in range(self.size - index): curr = curr.prev def addAtHead(self,val): pred = self.head succ = self.head.next self.size += 1 to_add = ListNode(val) to_add.prev = pred to_add.next = succ pred.next = to_add succ.prev = to_add def addAtTail(self,val): pred = self.tail.prev succ = self.tail self.size += 1 to_add = ListNode(val) to_add.next = succ to_add.prev = pred pred.next = to_add succ.prev = to_add def addAtIndex(self,index,val): if index > self.size: return if index < 0: index = 0 if index < self.size - index: pred = self.head for _ in range(index): pred = pred.next succ = pred.next else: succ = self.tail for _ in range(self.size - index): succ = succ.perv pred = succ.prev self.size += 1 to_add = ListNode(val) to_add.next = succ to_add.prev = pred pred.next = to_add succ.prev = to_add def deleteAtIndex(self,index): if index<0 or index>=self.size: return if index < self.size - index: pred = self.head for _ in range(index): pred = pred.next succ = pred.next.next else: succ = self.tail for _ in range(self.size-index): succ = succ.prev pred = succ.prev.prev self.size -= 1 pred.next = succ succ.prev = pred
2、移除链表中元素：
class ListNode: def __init__(self,val): self.val = val self.next = None class MyLinkedList: def __init__(self): self.size = 0 self.head = ListNode(0) def removeElements(self,target): cur = self.head while cur.next: if cur.next.val == target: cur.next = cur.next.next else: cur = cur.next return cur.next
3、链表翻转：
class Solution: def reverseList(self,head): cur = head pre = None while cur: temp = cur.next cur.next = pre #更新pre,cur指针 pre = cur cur = temp return pre
4、两两交换链表的节点：（模拟）
class ListNode: def __init__(self,val): self.val = val self.next = None class Solution: def swapPairs(self,head): res = ListNode(0) pre = res #pre为虚拟头，必须有pre的下一个与下下一个，否则交换结束 while pre.next and pre.next.next: cur = pre.next post = pre.next.next #pre,cur,post对应最左边，中间，最右边 cur.next = post.next pre.next = post post.next = cur pre = pre.next.next return res.next
5、删除链表倒数第n个节点：（双指针法）
class ListNode: def __init__(self,val): self.val = val self.next = None class Solution: def removeNthFromEnd(self,head,n): head_dummy = ListNode(0) head_dummy.next = head fast = head_dummy slow = head_dummy #先让fast指针向前走n步 while n!=0: fast = fast.next n -=1 while fast.next != None: slow = slow.next fast = fast.next #fast走到队尾后，slow的下一个节点为要删除的节点 slow.next = self.next.next return head_dummy.next
6、链表相交：
class ListNode: def __init__(self,val): self.val = val self.next = None class Solution: def getIntersectionNode(self,headA,headB): cur_a = headA cur_b = headB while cur_a != cur_b: cur_a = cur_a.next if cur_a else headB cur_b = cur_b.next if cur_b else headA return cur_a
7、环形链表：(注意第一次相遇，与第二次相遇的逻辑关系)
class Solution: def detect(self,head): slow = head fast = head while True: slow = slow.next fast = fast.next.next #如果相遇： if slow == fast: #将fast移动至head,slow不变，随后必在入口相遇 p = head q = slow while p != q: p = p.next q = q.next return p