当前位置:   article > 正文

python数据结构与算法——链表_listnode(0)

listnode(0)

1:两数相加 
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

分析:对应节点一一相加;注意进位

思路:%10计算当前位数字,//10计算进位值,flag进位标志位,创建一个哑节点作为返回的头节点

  1. class ListNode(object):
  2. def __init__(self,x):
  3. self.val=x
  4. self.next=None
  5. class Solution(object):
  6. def addTwoNumbers(self,l1,l2):
  7. """
  8. :type l1:ListNode
  9. :type l2:ListNode
  10. :rtype:ListNode
  11. """
  12. if l1 is None:
  13. return l2
  14. if l2 is None:
  15. return l1
  16. tmp=ListNode(0) #创建一个哑节点
  17. res=tmp #游标res
  18. flag=0 #加法运算的进位标志位
  19. while l1 or l2:
  20. tmpsum=0
  21. if l1:
  22. tmpsum=l1.val
  23. l1=l1.next
  24. if l2:
  25. tmpsum+=l2.val
  26. l2=l2.next
  27. tmpres=(tmpsum+flag)%10 #
  28. flag=(tmpsum+flag)//10 #更新加法运算的进位标志位
  29. res.next=ListNode(tmpres) #计算值赋予一个新的节点
  30. res=res.next #节点更新
  31. if flag: #这个是一种特殊情况 当出现最高位进位,
  32. res.next=ListNode(1)
  33. res=tmp.next #链表表头
  34. del tmp #释放节点tmp
  35. return res

2:链表的部分反转:

给定一个链表,翻转该链表从m到n的位置。要求直接翻转而非申请新空间。 如:给定1->2->3->4->5,m=2,n=4,返回1->4->3->2->5。假定给出的参数满足:1≤m≤n≤链表长度。

  1. #时间复杂度O(n),空间复杂度O(1)
  2. class ListNode(object):
  3. def __init__(self,x):
  4. self.val=x
  5. self.next=None
  6. class Solution:
  7. def ReverseList(head,m,n):
  8. if not head:
  9. return None
  10. #定义两个游标指针
  11. pre=None
  12. cur=head
  13. while m>1: #cur移动到要交换的节点,pre为cur前一个节点,注意这里m>1
  14. pre=cur
  15. cur=cur.next
  16. m-=1 #m移动到1
  17. n-=1 #n移动到m-n+1
  18. #定义两个新的游标指针,用于反转后链表与原链表的连接:
  19. tail=cur #初始化为链表的头部,为反转后链表的尾指针
  20. con=pre #为反转后链表的头指针
  21. #链表反转
  22. while n:
  23. t=cur.next # 这里用t来暂存cur.next节点
  24. cur.next=pre #反转
  25. pre=cur #前移pre
  26. cur=t
  27. n-=1
  28. #将反转链表与原链表相连接
  29. if con:
  30. con.next=pre
  31. else:#如果只有一个头节点
  32. head=pre
  33. tail.next=cur
  34. return head

3:链表划分:

给定一个链表和一个值x,将链表划分成两部分,使得划分后小于x的结点在前,大于等于x的结点在后。在这两部分中要保持原
链表中的出现顺序。如:给定链表1->4->3->2->5->2和x = 3,返回1->2->2->4->3->5

分析:遍历链表,小于x的放在一起

这样需要两个链表:一个存放小于x的节点;另一个存放相反状态。之后将两个链表连接在一起。

  1. class ListNode:
  2. def __init__(self, x):
  3. self.val = x
  4. self.next = None
  5. class Solution:
  6. def partition(self,head,x):
  7. #创建两个链表
  8. before_head=ListNode(0) #哑ListNode(0),before_head作用和head一样
  9. before=before_head #游标指针
  10. after_head=ListNode(0) #哑ListNode(0),after_head作用和head一样
  11. after=after_head #游标指针
  12. while head: #用head遍历链表,head为第一个节点
  13. if head.val<x: #小于x的存放在一个链表中
  14. before.next=head
  15. before=before.next
  16. else:#反之存放在另一个链表中
  17. after.next=head
  18. after=after.next
  19. head=head.next
  20. #两个链表拼接
  21. after.next=None
  22. before.next=after_head.next
  23. return before_head.next

4:删除排序链表中的重复元素

  1. class ListNode:
  2. def __init__(self, x):
  3. self.val = x
  4. self.next = None
  5. class Solution:
  6. def deleteDuplicates(self,head):
  7. if head==None or head.next==None:
  8. return head
  9. h=head #游标节点 因为要和h.next.next这个比较所以这里不再是head!=None,而是
  10. while h!=None:
  11. if h.val=h.next.val:
  12. h.next=h.next.next #删除操作
  13. #这里游标不后移
  14. else:
  15. h=h.next #游标后移(指针后移)
  16. return head

5:环形链表:

思路:判断一个链表是否为环形链表,见了快慢指针,当两者相遇时即为环形链表:

slow=slow.next

fast=fast.next.next

  1. class ListNode:
  2. def __init__(self,x):
  3. self.val=x
  4. self.next=None
  5. class Solution:
  6. def hasCycle(self, head):
  7. if not head or not head.next:
  8. return False
  9. slow=head#慢指针
  10. fast=head.next#快指针
  11. while slow!=fast: #循环结束标志 快慢指针相遇
  12. if fast==None:
  13. return False
  14. else:
  15. slow=slow.next #慢指针
  16. fast=fast.next.next#快指针
  17. return True

6:旋转链表

给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

  1. class Solution(object):
  2. def rotateRight(self, head, k):
  3. """
  4. :type head: ListNode
  5. :type k: int
  6. :rtype: ListNode
  7. """
  8. if not head or not head.next or not k:
  9. return head
  10. #创建一个哑节点
  11. a=ListNode(0)
  12. a.next=head
  13. #创建两个游标
  14. p1=a
  15. p2=a
  16. #计算节点数,并指向最后一个节点
  17. amount=0
  18. while p1.next:
  19. p1=p1.next
  20. amount+=1
  21. #计算旋转的前K个部分,并指向其末端节点
  22. n=amount-k%amount
  23. while n:
  24. p2=p2.next
  25. n-=1
  26. #改变指针的指向关系
  27. p1.next=a.next
  28. a.next=p2.next
  29. p2.next=None
  30. #
  31. return a.next
'
运行

7:合并两个有序链表

  1. # -*- coding: utf-8 -*-
  2. #输入:1->2->4, 1->3->4
  3. #输出:1->1->2->3->4->4
  4. # Definition for singly-linked list.
  5. # class ListNode(object):
  6. # def __init__(self, val=0, next=None):
  7. # self.val = val
  8. # self.next = next
  9. class Solution:
  10. def mergeTwoLists(self, l1, l2):
  11. prehead = ListNode(-1)
  12. prev = prehead
  13. while l1 and l2:
  14. if l1.val <= l2.val:
  15. prev.next = l1
  16. l1 = l1.next
  17. else:
  18. prev.next = l2
  19. l2 = l2.next
  20. prev = prev.next
  21. # 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
  22. prev.next = l1 if l1 is not None else l2
  23. return prehead.next

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/859355
推荐阅读
相关标签
  

闽ICP备14008679号