赞
踩
1:两数相加
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
分析:对应节点一一相加;注意进位
思路:%10计算当前位数字,//10计算进位值,flag进位标志位,创建一个哑节点作为返回的头节点
- class ListNode(object):
- def __init__(self,x):
- self.val=x
- self.next=None
- class Solution(object):
- def addTwoNumbers(self,l1,l2):
- """
- :type l1:ListNode
- :type l2:ListNode
- :rtype:ListNode
- """
- if l1 is None:
- return l2
- if l2 is None:
- return l1
-
- tmp=ListNode(0) #创建一个哑节点
- res=tmp #游标res
-
- flag=0 #加法运算的进位标志位
- while l1 or l2:
- tmpsum=0
- if l1:
- tmpsum=l1.val
- l1=l1.next
-
- if l2:
- tmpsum+=l2.val
- l2=l2.next
-
- tmpres=(tmpsum+flag)%10 #
- flag=(tmpsum+flag)//10 #更新加法运算的进位标志位
-
-
- res.next=ListNode(tmpres) #计算值赋予一个新的节点
-
-
- res=res.next #节点更新
-
-
- if flag: #这个是一种特殊情况 当出现最高位进位,
- res.next=ListNode(1)
-
-
- res=tmp.next #链表表头
- del tmp #释放节点tmp
- return res

给定一个链表,翻转该链表从m到n的位置。要求直接翻转而非申请新空间。 如:给定1->2->3->4->5,m=2,n=4,返回1->4->3->2->5。假定给出的参数满足:1≤m≤n≤链表长度。
- #时间复杂度O(n),空间复杂度O(1)
- class ListNode(object):
- def __init__(self,x):
- self.val=x
- self.next=None
-
- class Solution:
- def ReverseList(head,m,n):
- if not head:
- return None
-
- #定义两个游标指针
- pre=None
- cur=head
-
- while m>1: #cur移动到要交换的节点,pre为cur前一个节点,注意这里m>1
- pre=cur
- cur=cur.next
- m-=1 #m移动到1
- n-=1 #n移动到m-n+1
-
- #定义两个新的游标指针,用于反转后链表与原链表的连接:
- tail=cur #初始化为链表的头部,为反转后链表的尾指针
- con=pre #为反转后链表的头指针
-
- #链表反转
- while n:
- t=cur.next # 这里用t来暂存cur.next节点
- cur.next=pre #反转
- pre=cur #前移pre
- cur=t
- n-=1
-
- #将反转链表与原链表相连接
-
- if con:
- con.next=pre
- else:#如果只有一个头节点
- head=pre
-
- tail.next=cur
-
- return head

给定一个链表和一个值x,将链表划分成两部分,使得划分后小于x的结点在前,大于等于x的结点在后。在这两部分中要保持原
链表中的出现顺序。如:给定链表1->4->3->2->5->2和x = 3,返回1->2->2->4->3->5
分析:遍历链表,小于x的放在一起
这样需要两个链表:一个存放小于x的节点;另一个存放相反状态。之后将两个链表连接在一起。
- class ListNode:
- def __init__(self, x):
- self.val = x
- self.next = None
-
- class Solution:
- def partition(self,head,x):
-
- #创建两个链表
- before_head=ListNode(0) #哑ListNode(0),before_head作用和head一样
- before=before_head #游标指针
-
- after_head=ListNode(0) #哑ListNode(0),after_head作用和head一样
- after=after_head #游标指针
-
-
- while head: #用head遍历链表,head为第一个节点
-
- if head.val<x: #小于x的存放在一个链表中
- before.next=head
- before=before.next
- else:#反之存放在另一个链表中
- after.next=head
- after=after.next
-
- head=head.next
-
- #两个链表拼接
- after.next=None
- before.next=after_head.next
-
- return before_head.next

- class ListNode:
- def __init__(self, x):
- self.val = x
- self.next = None
-
- class Solution:
- def deleteDuplicates(self,head):
- if head==None or head.next==None:
- return head
- h=head #游标节点 因为要和h.next.next这个比较所以这里不再是head!=None,而是
- while h!=None:
- if h.val=h.next.val:
- h.next=h.next.next #删除操作
- #这里游标不后移
- else:
- h=h.next #游标后移(指针后移)
- return head

思路:判断一个链表是否为环形链表,见了快慢指针,当两者相遇时即为环形链表:
slow=slow.next
fast=fast.next.next
- class ListNode:
- def __init__(self,x):
- self.val=x
- self.next=None
-
- class Solution:
- def hasCycle(self, head):
- if not head or not head.next:
- return False
- slow=head#慢指针
- fast=head.next#快指针
- while slow!=fast: #循环结束标志 快慢指针相遇
- if fast==None:
- return False
- else:
- slow=slow.next #慢指针
- fast=fast.next.next#快指针
- return True

给定一个链表,旋转链表,将链表每个节点向右移动 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
- class Solution(object):
- def rotateRight(self, head, k):
- """
- :type head: ListNode
- :type k: int
- :rtype: ListNode
- """
- if not head or not head.next or not k:
- return head
- #创建一个哑节点
- a=ListNode(0)
- a.next=head
-
- #创建两个游标
- p1=a
- p2=a
-
- #计算节点数,并指向最后一个节点
- amount=0
- while p1.next:
- p1=p1.next
- amount+=1
-
- #计算旋转的前K个部分,并指向其末端节点
- n=amount-k%amount
- while n:
- p2=p2.next
- n-=1
-
- #改变指针的指向关系
- p1.next=a.next
- a.next=p2.next
- p2.next=None
-
- #
- return a.next
'运行
7:合并两个有序链表
- # -*- coding: utf-8 -*-
- #输入:1->2->4, 1->3->4
- #输出:1->1->2->3->4->4
-
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, val=0, next=None):
- # self.val = val
- # self.next = next
-
- class Solution:
- def mergeTwoLists(self, l1, l2):
- prehead = ListNode(-1)
-
- prev = prehead
- while l1 and l2:
- if l1.val <= l2.val:
- prev.next = l1
- l1 = l1.next
- else:
- prev.next = l2
- l2 = l2.next
- prev = prev.next
-
- # 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
- prev.next = l1 if l1 is not None else l2
-
- return prehead.next

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。