• 知识储备--基础算法篇-链表


    1.链表

    链表在python中是可以自定义的,属性包括val和next。一般表示链表都是用头节点表示,得到下一个节点用next,都是地址,想要得到值用val。

    1.1第160题-相交链表

    简单来说,就是求两个链表交点节点的 指针。 这里要注意,交点不是数值相等,而是指针相等。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, x):
    4. # self.val = x
    5. # self.next = None
    6. class Solution(object):
    7. def getIntersectionNode(self, headA, headB):
    8. """
    9. :type head1, head1: ListNode
    10. :rtype: ListNode
    11. """
    12. # 用顺序遍历的方法
    13. p, q = headA, headB
    14. # 先得到两个链表的长度
    15. lenA = 0
    16. lenB = 0
    17. while p != None:
    18. p = p.next
    19. lenA += 1
    20. while q != None:
    21. q = q.next
    22. lenB += 1
    23. # 尾部对齐
    24. # 再次将pq对准链表头节点
    25. p, q = headA, headB
    26. if lenA < lenB:
    27. temp = lenB - lenA
    28. while temp != 0:
    29. q = q.next
    30. temp -= 1
    31. else:
    32. temp = lenA - lenB
    33. while temp != 0:
    34. p = p.next
    35. temp -= 1
    36. # 同时向后遍历
    37. len_min = min(lenA, lenB)
    38. for i in range(len_min):
    39. if p == q:
    40. return p
    41. else:
    42. p = p.next
    43. q = q.next
    44. return None

    看了解析,自己用倒序法做做试试。 

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, x):
    4. # self.val = x
    5. # self.next = None
    6. class Solution(object):
    7. def getIntersectionNode(self, headA, headB):
    8. """
    9. :type head1, head1: ListNode
    10. :rtype: ListNode
    11. """
    12. # 用倒序遍历的方法
    13. # 用栈,先将地址顺序存进去,然后倒着遍历
    14. p, q = headA, headB
    15. # 先得到两个链表的长度
    16. lenA = 0
    17. lenB = 0
    18. listA = []
    19. listB = []
    20. while p != None:
    21. listA.append(p)
    22. p = p.next
    23. lenA += 1
    24. while q != None:
    25. listB.append(q)
    26. q = q.next
    27. lenB += 1
    28. len_min = min(lenA, lenB)
    29. result = None
    30. for i in range(len_min):
    31. if listA[lenA-1-i] == listB[lenB-1-i]:
    32. result = listA[lenA-1-i]
    33. else:
    34. return result
    35. return result

    1.2第206题-反转链表

    给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

    心得:若节点被引用,如p=head,这时改变head会使p也改变。所以需要提前存储节点。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def reverseList(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: ListNode
    11. """
    12. # 值反转还是地址反转
    13. # 地址反转,因为读取链表的值需要一直遍历得到
    14. length = 0
    15. p = head
    16. q = head
    17. list_ = []
    18. while p != None:
    19. list_.append(p)
    20. length += 1
    21. q = p
    22. p = p.next
    23. p = head
    24. # 需要倒序遍历储存了节点地址的列表
    25. for i in reversed(range(length)):
    26. if i == 0:
    27. list_[i].next = None
    28. else:
    29. list_[i].next = list_[i-1]
    30. return q

    一开始就想的这个方法,可惜不知道怎么实现。 

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def reverseList(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: ListNode
    11. """
    12. pre = None
    13. cur = head
    14. while cur != None:
    15. nex = cur.next
    16. cur.next = pre
    17. pre = cur
    18. cur = nex
    19. return pre

    1.3第234题-回文链表

    第一时间想的就是把节点的值都存储到数组中,然后直接判断数组是否回文。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def isPalindrome(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: bool
    11. """
    12. p = head
    13. length = 0
    14. values = []
    15. while p != None:
    16. values.append(p.val)
    17. length += 1
    18. p = p.next
    19. for i in range(length/2):
    20. if values[i] == values[length-i-1]:
    21. continue
    22. else:
    23. return False
    24. return True

    用快慢指针的方法能够节省很多空间

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def isPalindrome(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: bool
    11. """
    12. p = head
    13. # 用快慢指针
    14. fast = head
    15. slow = head
    16. # 1.找到前半部分尾节点
    17. while fast != None:
    18. if fast.next == None:
    19. break
    20. elif fast.next.next == None:
    21. break
    22. slow = slow.next
    23. fast = fast.next.next
    24. # 慢指针为前半部分的尾节点
    25. # 2.反转后半部分链表
    26. pre = None
    27. cur = slow
    28. while cur != None:
    29. nex = cur.next
    30. cur.next = pre
    31. pre = cur
    32. cur = nex
    33. # 3.判断是否回文
    34. while p != None:
    35. val1 = p.val
    36. val2 = pre.val
    37. if val1 != val2:
    38. return False
    39. p = p.next
    40. pre = pre.next
    41. # 4.恢复链表,和第二步一样操作
    42. # 5.返回结果
    43. return True

    1.4第141题-环形链表

    给你一个链表的头节点 head ,判断链表中是否有环。

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

    如果链表中存在环 ,则返回 true 。 否则,返回 false 。

    心得:想到哈希表,虽然ac了,但时间跟空间都不行。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, x):
    4. # self.val = x
    5. # self.next = None
    6. class Solution(object):
    7. def hasCycle(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: bool
    11. """
    12. # 第一时间想到用字典,键值名是节点地址,键值是索引
    13. # 不需要返回环在第几个,可以用哈希表
    14. hash_table = set()
    15. p = head
    16. while p != None:
    17. if p in hash_table:
    18. return True
    19. else:
    20. hash_table.add(p)
    21. p = p.next
    22. return False

    思考:环形链表有尾节点吗,有地址是None的情况吗。 

    答:没有尾节点,地址没有None的情况。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, x):
    4. # self.val = x
    5. # self.next = None
    6. class Solution(object):
    7. def hasCycle(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: bool
    11. """
    12. # 快慢指针?
    13. # 慢指针记录当前地址和前一个地址
    14. # 当快指针的地址与这两个相同时即存在环形链表
    15. if head == None:
    16. return False
    17. elif head.next == None:
    18. return False
    19. pre = None
    20. slow = head
    21. fast = head.next
    22. while slow != None:
    23. if fast == pre or fast == slow:
    24. return True
    25. if fast.next==None or fast.next.next==None:
    26. return False
    27. pre = slow
    28. slow = slow.next
    29. fast = fast.next.next
    30. return False

    因为环形链表没有None,所以暴力解法。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, x):
    4. # self.val = x
    5. # self.next = None
    6. class Solution(object):
    7. def hasCycle(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: bool
    11. """
    12. # 因为环形链表没有None
    13. # 且数目最大是10**4
    14. p = head
    15. length = 0
    16. while 1:
    17. if p == None:
    18. return False
    19. else:
    20. length += 1
    21. p = p.next
    22. if length > 10000:
    23. return True

    1.5第142题-环形链表2

    给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

    不允许修改 链表。

    示例 1:

    心得:还是先用哈希表做。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, x):
    4. # self.val = x
    5. # self.next = None
    6. class Solution(object):
    7. def detectCycle(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: ListNode
    11. """
    12. # 用哈希表记录地址
    13. hash_table = set()
    14. p = head
    15. while p != None:
    16. if p not in hash_table:
    17. hash_table.add(p)
    18. else:
    19. return p
    20. p = p.next

    看了题解,用快慢指针做,太复杂了,纯考数学啊。 

    1.6第21题-合并两个有序链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

    示例 1:

    可以先创建一个val为-1的单链表,然后在其基础上拓展。思路还是挺简单的。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def mergeTwoLists(self, list1, list2):
    8. """
    9. :type list1: Optional[ListNode]
    10. :type list2: Optional[ListNode]
    11. :rtype: Optional[ListNode]
    12. """
    13. # 比较val的大小,然后决定next的地址
    14. # 头指针
    15. neww = ListNode(-1)
    16. # 移动指针
    17. new = neww
    18. while 1:
    19. if list1 == None:
    20. while list2 != None:
    21. new.next = list2
    22. new = new.next
    23. list2 = list2.next
    24. break
    25. elif list2 == None:
    26. while list1 != None:
    27. new.next = list1
    28. new = new.next
    29. list1 = list1.next
    30. break
    31. if list1.val <= list2.val:
    32. new.next = list1
    33. list1 = list1.next
    34. else:
    35. new.next = list2
    36. list2 = list2.next
    37. new = new.next
    38. return neww.next

    1.7第2题-两数相加

    给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

    请你将两个数相加,并以相同形式返回一个表示和的链表。

    你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

    示例 1:

    心得:逻辑挺简单的就是进位注意不要遗忘。 

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def addTwoNumbers(self, l1, l2):
    8. """
    9. :type l1: ListNode
    10. :type l2: ListNode
    11. :rtype: ListNode
    12. """
    13. neww = ListNode(-1)
    14. new = neww
    15. up = 0
    16. while l1 != None or l2 != None:
    17. if l1 != None and l2 != None:
    18. if l1.val + l2.val + up < 10:
    19. temp = ListNode(l1.val + l2.val + up)
    20. up = 0
    21. else:
    22. temp = ListNode((l1.val + l2.val + up)%10)
    23. up = 1
    24. l1 = l1.next
    25. l2 = l2.next
    26. elif l1 == None:
    27. if l2.val + up < 10:
    28. temp = ListNode(l2.val + up)
    29. up = 0
    30. else:
    31. temp = ListNode(0)
    32. up = 1
    33. l2 = l2.next
    34. elif l2 == None:
    35. if l1.val + up < 10:
    36. temp = ListNode(l1.val + up)
    37. up = 0
    38. else:
    39. temp = ListNode(0)
    40. up = 1
    41. l1 = l1.next
    42. new.next = temp
    43. new = new.next
    44. if up == 1:
    45. temp = ListNode(1)
    46. new.next = temp
    47. new = new.next
    48. return neww.next

    1.8第19题-删除链表的倒数第 N 个结点

    给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

    示例 1:

    先试试第三种方法 

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def removeNthFromEnd(self, head, n):
    8. """
    9. :type head: ListNode
    10. :type n: int
    11. :rtype: ListNode
    12. """
    13. # 几种方法
    14. # 1、先翻转,再删除第n个节点,再翻转
    15. # 2、计算长度,然后再遍历一遍,删掉节点
    16. # 3、计算长度并将地址存入数组,直接索引删除节点
    17. p = head
    18. index = []
    19. length = 0
    20. while p != None:
    21. length += 1
    22. index.append(p)
    23. p = p.next
    24. target = length - n
    25. if target == 0:
    26. return head.next
    27. if n == 1:
    28. index[target-1].next = None
    29. else:
    30. index[target-1].next = index[target+1]
    31. return head

    再试试第二种

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def removeNthFromEnd(self, head, n):
    8. """
    9. :type head: ListNode
    10. :type n: int
    11. :rtype: ListNode
    12. """
    13. # 几种方法
    14. # 1、先翻转,再删除第n个节点,再翻转
    15. # 2、计算长度,然后再遍历一遍,删掉节点
    16. # 3、计算长度并将地址存入数组,直接索引删除节点
    17. p = head
    18. length = 0
    19. while p != None:
    20. length += 1
    21. p = p.next
    22. target = length - n
    23. num = 0
    24. if target == 0:
    25. return head.next
    26. p = head
    27. while p != None:
    28. num += 1
    29. if num == target:
    30. p.next = p.next.next
    31. break
    32. p = p.next
    33. return head

    第一种时间复杂度太高,就不试了。

    看了解析,这种倒数第几个的方式应该要想到用栈来做,弹出的第n个节点就为需要删除的节点了。 

    哑节点的设置

    dummy = ListNode(0, head)

    心得:看到一个双指针的方法,用两个指针,中间相差n,当一个指针到达尾部时,另一个就在目标位置,删除即可,没想到,可惜。 

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def removeNthFromEnd(self, head, n):
    8. """
    9. :type head: ListNode
    10. :type n: int
    11. :rtype: ListNode
    12. """
    13. count = 0
    14. dummy_note = ListNode(0,head)
    15. fast = dummy_note
    16. slow = dummy_note
    17. while fast != None:
    18. if count > n:
    19. slow = slow.next
    20. count += 1
    21. fast = fast.next
    22. slow.next = slow.next.next
    23. return dummy_note.next

    时间太长了吧。 

    1.9第24题-两两交换链表中的节点

    心得:节点的地址永远不变,但表示地址的变量随时可以改变。要注意,要赋值的地址在上一两行不能改变,不然就混乱了,要合理安排赋值的顺序。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def swapPairs(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: ListNode
    11. """
    12. # 1、把地址全存下来改
    13. # 2、遍历一遍并修改
    14. # 局部翻转链表
    15. # 两两交换需要三步
    16. if head == None:
    17. return head
    18. elif head.next == None:
    19. return head
    20. pre = ListNode(0,head)
    21. result = pre
    22. cur = head
    23. while cur:
    24. if cur.next == None:
    25. break
    26. back = cur.next
    27. cur.next = back.next
    28. back.next = cur
    29. pre.next = back
    30. pre = cur
    31. cur = cur.next
    32. return result.next

    1.10第138题-复制带随机指针的链表

    1. """
    2. # Definition for a Node.
    3. class Node:
    4. def __init__(self, x, next=None, random=None):
    5. self.val = int(x)
    6. self.next = next
    7. self.random = random
    8. """
    9. class Solution(object):
    10. def copyRandomList(self, head):
    11. """
    12. :type head: Node
    13. :rtype: Node
    14. """
    15. if head == None:
    16. return None
    17. p = head
    18. q = head.next
    19. result = Node(p.val)
    20. cur = result
    21. i = result
    22. # 先生成单链表
    23. # 用双循环,当外层指针的random等于内层指针地址时,新链表的random也等于这个位置的地址
    24. while q:
    25. back = Node(q.val)
    26. cur.val = p.val
    27. cur.next = back
    28. cur = cur.next
    29. p = p.next
    30. q = q.next
    31. p = head
    32. k = result
    33. while p:
    34. i = result
    35. j = head
    36. while i:
    37. if p.random == None:
    38. k.random = None
    39. break
    40. if p.random == j:
    41. k.random = i
    42. i = i.next
    43. j = j.next
    44. p = p.next
    45. k = k.next
    46. return result

    在题解评论中看到一个很巧妙的方法,试了一下确实很通俗易懂。 

    1. """
    2. # Definition for a Node.
    3. class Node:
    4. def __init__(self, x, next=None, random=None):
    5. self.val = int(x)
    6. self.next = next
    7. self.random = random
    8. """
    9. class Solution(object):
    10. def copyRandomList(self, head):
    11. """
    12. :type head: Node
    13. :rtype: Node
    14. """
    15. if head == None:
    16. return None
    17. # 将新老节点地址储存在一起,遍历得到对应的next和random
    18. store = {}
    19. p = head
    20. while p:
    21. store[p] = Node(p.val)
    22. p = p.next
    23. p = head
    24. while p:
    25. if p.next == None:
    26. store[p].next = None
    27. else:
    28. store[p].next = store[p.next]
    29. if p.random == None:
    30. store[p].random = None
    31. else:
    32. store[p].random = store[p.random]
    33. p = p.next
    34. return store[head]

    1.11第148题-排序链表

    给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

    示例 1:

    输入:head = [4,2,1,3]
    输出:[1,2,3,4]

    心得:想法是地址随着val排序,结果超时了。 

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def sortList(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: ListNode
    11. """
    12. if head == None:
    13. return None
    14. # 把地址和对应的val存储起来
    15. # 先排序val,然后相应的地址也会改变
    16. p = head
    17. addrees = []
    18. length = 0
    19. while p:
    20. length += 1
    21. addrees.append(p)
    22. p = p.next
    23. for i in range(length):
    24. j = 0
    25. while j < length - i - 1:
    26. if addrees[j].val > addrees[j+1].val:
    27. temp_addrees = addrees[j]
    28. addrees[j] = addrees[j+1]
    29. addrees[j+1] = temp_addrees
    30. j += 1
    31. dummy = ListNode(0)
    32. head = addrees[0]
    33. dummy.next = head
    34. for i in range(1,length):
    35. head.next = addrees[i]
    36. head = head.next
    37. head.next = None
    38. return dummy.next

    链表适合归并排序,冒泡、插入、归并都必须掌握。

    1. # Definition for singly-linked list.
    2. # class ListNode(object):
    3. # def __init__(self, val=0, next=None):
    4. # self.val = val
    5. # self.next = next
    6. class Solution(object):
    7. def sortList(self, head):
    8. """
    9. :type head: ListNode
    10. :rtype: ListNode
    11. """
    12. def sortFunc(head, tail):
    13. if not head:
    14. return head
    15. if head.next == tail:
    16. head.next = None
    17. return head
    18. slow = fast = head
    19. while fast != tail:
    20. slow = slow.next
    21. fast = fast.next
    22. if fast != tail:
    23. fast = fast.next
    24. mid = slow
    25. return merge(sortFunc(head, mid), sortFunc(mid, tail))
    26. def merge(head1, head2):
    27. dummyHead = ListNode(0)
    28. temp, temp1, temp2 = dummyHead, head1, head2
    29. while temp1 and temp2:
    30. if temp1.val <= temp2.val:
    31. temp.next = temp1
    32. temp1 = temp1.next
    33. else:
    34. temp.next = temp2
    35. temp2 = temp2.next
    36. temp = temp.next
    37. if temp1:
    38. temp.next = temp1
    39. elif temp2:
    40. temp.next = temp2
    41. return dummyHead.next
    42. return sortFunc(head, None)

  • 相关阅读:
    一起学数据结构(9)——二叉树的链式存储及相关功能实现
    嵌入式分享合集113
    Springboot启动流程(源码解析)、自动装配流程(源码解析)、总结、SrpringBoot初始化数据扩展
    2020年五一杯数学建模C题饲料混合加工问题解题全过程文档及程序
    react简单的服务器渲染示例(含redux, redux-thunk的使用)
    【无标题】
    javascript数组排序
    使用 WebGL 创建 3D 对象
    【codeforces】1673C. Palindrome Basis(DP划分,回文数判定)
    【Vue】vue2适配移动端 vue创建移动端项目
  • 原文地址:https://blog.csdn.net/Orange_sparkle/article/details/132766265