题目:
链表的数据格式就是如下:
需要注意的是:链表尾部的next为None
。所以判断链表结束时,这是遍历一个链表最常用的结束方式
。使用的代码:
while p != None: p = p.next
其实是当p已经指向了next区域,这时next为空,所以能够退出
当使用p.next != None
时,这时p指向的最有一个节点,而不是节点的next。
while p.next != None: p = p.next
删除节点两种方式:
当前节点指向下下个节点
将下一个节点赋值给当前节点,然后删除下一个节点
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteNode(self, node): """ :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. """ node.val,node.next.val = node.next.val,node.val node.next = node.next.next
有两种方式:
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: # 设置头结点 re = ListNode(-1) re.next = head slow = re fast = slow while n + 1> 0: fast = fast.next n -= 1 while fast != None: fast = fast.next slow = slow.next slow.next = slow.next.next return re.next
使用双指针可以将链表逆序。
class Solution: def reverseList(self, head: ListNode) -> ListNode: pre = None cur = head while cur: temp = cur.next # 先把原来cur.next位置存起来 cur.next = pre pre = cur cur = temp return pre
需要注意结束条件。当cur == None
时,pre刚好在链尾的位置。返回pre就是返回了新的链表
请判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题? 作者:力扣 (LeetCode) 链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/
回文最常用的判断方式是:
链表回文有多种方式:
class Solution: def isPalindrome(self, head: ListNode) -> bool: if not head or not head.next: return True slow = head fast = head mystack = [] while fast and fast.next: mystack.append(slow.val) fast = fast.next.next slow = slow.next # 奇数状态,需要跨过中间的元素 if fast: slow = slow.next while slow and slow.val == mystack.pop(): slow = slow.next
判断链表是否有环路有两个解决方法,
第一:快慢指针,如果存在环路,快指针一定会追上慢指针
第二:字典。将遍历过的节点存入到字典中,每次遍历时在字典中查找,如果存在则表明有环路。
class Node(): def __init__(self, data): self.data = data self.next = None node1 = Node(100) node2 = Node(200) node3 = Node(300) node4 = Node(300) node5 = Node(200) node6 = Node(100) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node6 node6.next = node1 def cycle_link(head): fast = head slow = head while fast and fast.next: fast = fast.next.next slow = slow.next if fast == slow: return True return False res = cycle_link(node1) print(res)
class Solution: def hasCycle(self, head: ListNode) -> bool: if not head: return False Hash = {} temp = head while temp != None: if Hash.get(temp): return True else: Hash[temp] = True temp = temp.next return False
通过计算可以知道,快指针走的距离是慢指针距离的两倍,同时快指针比慢指针多走了一个圆的距离。所以在快慢指针相遇的地方,两个指针以相同的数据在走下去,相遇的地方就是环的入口
class Solution: def detectCycle(self, head: ListNode) -> ListNode: first = head second = head while first and first.next: first = first.next.next second = second.next if first == second: first = head while True: if first == second: return first first = first.next second = second.next return None
使用链表这样数据结构实现排序,归并排序的实现如下:
先分开,后合并
def sortList(self, head: ListNode) -> ListNode: if not head or not head.next: return head slow = head fast = head # 用快慢指针分成两部分 while fast.next and fast.next.next: slow = slow.next fast = fast.next.next # 找到左右部分, 把左部分最后置空 mid = slow.next slow.next = None # 递归下去 left = self.sortList(head) right = self.sortList(mid) # 合并 return self.merge(left, right) def merge(self, left, right): dummy = ListNode(0) p = dummy l = left r = right while l and r: if l.val < r.val: p.next = l l = l.next p = p.next else: p.next = r r = r.next p = p.next if l: p.next = l if r: p.next = r return dummy.next
编写一个程序,找到两个单链表相交的起始节点。
在节点 c1 开始相交。
原理:两个链表是否有相交的地方,可以通过如下方法测试出来:
走完A之后,从B起始点开始走,同样,走完B之后,从A开始走,这样如果有相交的位置,那么A和B到相交的位置就刚好一致。
class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: if not(headA and headB): return None nodea = headA nodeb = headB while nodea != nodeb: if nodea is None: nodea = headB else: nodea = nodea.next if nodeb is None: nodeb = headA else: nodeb = nodeb.next return nodea
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
输入:head = [1,2,3,4]
输出:[2,1,4,3]
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def swapPairs(self, head: ListNode) -> ListNode: pre_head = ListNode(-1) pre_head.next = head pre_h = pre_head p = head while p and p.next: next_p = p.next p.next = next_p.next pre_h.next = next_p next_p.next = p pre_h = p p = p.next return pre_head.next
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。
class Solution: def addInList(self , head1 , head2 ): def reverse_fun(head): pre = None p = head while p: temp = p.next p.next = pre pre = p p = temp return pre re_head1 = reverse_fun(head1) re_head2 = reverse_fun(head2) d = ListNode(0) p = d c = 0 while re_head1 or re_head2 or c: if re_head1: c += re_head1.val re_head1 = re_head1.next if re_head2: c += re_head2.val re_head2 = re_head2.next p.next = ListNode(c % 10) p = p.next c = c // 10 return reverse_fun(d.next)
链表是我喜欢的数据结构,因为链表没有太多复杂操作。通常是遍历链表一直到尾节点,然后一边遍历一边配合指针操作。在链表中有几个小技巧可以好好总结一下:
while first and first.next: first = first.next.next second = second.next
带头结点的指针更好操作。在函数中,创建一个带头结点指针更方便操作。
node = ListNode(None)
使用场景:删除节点,翻转节点
链表取奇偶很简单,next的next就能保证奇偶