楼市新闻、行业动态
叭楼，新房带看，二手房代办过户，望京二手房精选房源，您置业的小管家。
声明：本站内容来源于网络或叭楼会员发布，叭楼只作为信息发布平台，版权归原作者所有，本站不承担任何图片、内容、观点等内容版权问题，如对内容有歧义，可第一时间联系本站管理员发送邮件8309272@qq.com或者扫码微信沟通，经核实后我们会第一时间删除。
北京二手房、楼市分析
链表的简单题我是一天刷完的，题号五六百以后的基本上没怎么做，中等题基本上每天刷两三个的速度，一共11个。有些链表问题没有写到这一篇，比如链表的排序在排序篇。2. 两数相加给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序…
链表的简单题我是一天刷完的，题号五六百以后的基本上没怎么做，中等题基本上每天刷两三个的速度，一共11个。有些链表问题没有写到这一篇，比如链表的排序在排序篇。
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807思路
讨论l1、l2为空的情况，考虑进位（除以和取余），考虑l1或l2链表长的情况。
代码
# Definition for singly-linked list.
# 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 == None:
return l2
if l2 == None:
return l1
carry = 0
head = ListNode(0);
p = head
while l1 and l2:
p.next = ListNode( (l1.val+l2.val+carry) % 10)
carry = (l1.val+l2.val+carry) // 10
l1 = l1.next
l2 = l2.next
p = p.next
if l2:
while l2:
p.next = ListNode((l2.val +carry) % 10)
carry = (l2.val + carry) // 10
l2 = l2.next
p = p.next
if l1:
while l1:
p.next = ListNode((l1.val +carry) % 10)
carry = (l1.val + carry) // 10
l1 = l1.next
p = p.next
if carry == 1:
p.next = ListNode(1)
return head.next19. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.思路
借助列表存储链表的所有节点，考虑特殊情况，如果链表长度为1，删除后返回None，如果链表长度为n，即为删除倒数第n个（第一个）节点。
列表中可以取负值，li[-n] : 读取列表中倒数第n个元素
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
nlist = []
while head: #先将全部节点存在列表里
nlist.append(head)
head = head.next
if len(nlist)==1: #列表长度为1
return None
elif len(nlist)==n: #相当于删除第一个（倒数第n个）
nlist.pop(0)
return nlist[0]
nlist[-n-1].next = nlist[-n].next
nlist.pop(-n)
return nlist[0]24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.思路
用列表存储结点的值，通过索引两两交换，在列表中完成数值的交换，然后将这些值以链表的形式连起来。
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
if head.next == None:
return head
li = []
while head != None:
li.append(head.val)
head = head.next
k = 0
while k + 1 < len(li): #列表中完成两两交换
t = li[k]
li[k] = li[k+1]
li[k+1] = t
k=k+2
n1 = ListNode(li[0])
n2 = ListNode(li[1])
n1.next = n2
for j in range(2,len(li)):
n3 = ListNode(li[j])
n2.next = n3
n2 = n2.next
return n161. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 :
输入: 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思路
首先计算链表的长度，然后计算链表经过k步的移动后，新的头结点在哪，最后虚拟头结点连接新的头结点。
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head == None or k == 0:
return head
dummy = ListNode(-1) #设置虚拟头结点
dummy.next = head
cur = dummy #指针指向虚拟头结点
length = 0 #计算链表长度
while cur.next: #得到链表的长度
length+=1
cur = cur.next
cur.next = dummy.next #此时的尾节点指向头结点
count = length - (k%length) #得到新的head的位置
while count > 0: #移动到新head的位置
count= count-1
cur = cur.next
dummy.next = cur.next #虚拟头结点链接新头结点
cur.next = None
return dummy.next82. 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 :
输入: 1->2->3->3->4->4->5
输出: 1->2->5思路
1.设置一个虚拟头结点，设置两个指针，pre指向虚拟头结点，cur指向头结点。
2.判断下一个节点的值和cur的值是否相等，若相等cur后移，直到下个节点的值和cur的值不同。
3.此时执行pre.next= cur.next。
4.继续走直到结尾.
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
pre = dummy
cur = head
while cur:
while cur.next and cur.val == cur.next.val:
cur = cur.next
if pre.next == cur:
pre = pre.next
else:
pre.next = cur.next
cur = cur.next
return dummy.next86. 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5思路
构建两个新的链表，将小于x的放在一个链表，将大于等于x的放在另一个链表，最后连起来。
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
min_head = ListNode(0)
max_head = ListNode(0)
i_head = min_head
a_head = max_head
while head:
if head.val < x:
min_head.next = ListNode(head.val)
min_head = min_head.next
else:
max_head.next = ListNode(head.val)
max_head = max_head.next
head = head.next
min_head.next = a_head.next
return i_head.next92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL思路
分三段考虑，反转前，只需要记录反转点即可；反转段，链表反转；最后连接剩余段。
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
bf_head = head
i = 1
pre_head = None
#反转前
while i < m:
pre_head = head
head = head.next
i += 1
#反转段
new_head = None
tial = head
while i <= n:
tmp = head.next
head.next = new_head
new_head = head
head = tmp
i += 1
#反转后段
if pre_head:
pre_head.next = new_head
else:
bf_head = new_head
tial.next = head
return bf_head142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 ：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
思路
设置快慢指针，快指针是慢指针的几倍，就会转几圈与慢指针相遇。
相遇点距环入口的距离，等于头结点距环入口的距离。
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
if head.next == None:
return None
fast = slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
p = head
while slow != p:
p = p.next
slow = slow.next
return p
return None143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 :
给定链表 1->2->3->4, 重新排列为 1->4->2->3.思路
快慢指针找到中点，后半部分链表反转，插入前半部分。
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
if head == None:
return None
if head.next == None:
return head
fast = head
slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
front = slow.next
slow.next = None
#反转链表
last = None
mid = None
while front.next:
mid = front
front = front.next
mid.next = last
last = mid
front.next = mid
#链表的合并
first = head
result = first
second = front
while first.next != None:
temp = first
first = first.next
temp.next = second
temp = temp.next
second = second.next
temp.next = first
if second != None:
first.next = second
head = result
return head328. 奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 :
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL思路
奇偶双指针交叉，最后连在一起。
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def oddEvenList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return head
odd = odd_head = head
even = even_head =head.next
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return odd_head445. 两数相加 II
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7思路
借助列表，将l1和l2都存入列表中，列表短的在首位补0，保证列表对齐。然后按位相加，最后存入链表。
代码
# Definition for singly-linked list.
# 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
"""
a = []
b = []
while l1:
a.append(l1.val)
l1 = l1.next
while l2:
b.append(l2.val)
l2 = l2.next
tag = 0
c= []
maxlen = max(len(a),len(b))
if len(a) < maxlen:
for i in range(maxlen - len(a)):
a.insert(0,0)
if len(b) < maxlen:
for i in range(maxlen - len(b)):
b.insert(0,0)
for i in range(0,maxlen):
sum = a[maxlen - i -1] + b[maxlen - i -1] + tag
if sum >= 10:
tag = 1
else:
tag = 0
c.insert(0, sum%10)
if tag == 1:
c.insert(0,1)
l3 = ListNode(c[0])
node = l3
for i in range(1,len(c)):
node.next = ListNode(c[i])
node = node.next
node.next = None
return l3© 版权声明
声明：本站内容来源于网络或叭楼会员发布，网站只作为信息发布平台，版权归原作者所有，本站不承担任何图片、内容、观点等内容版权问题，如对内容有歧义，可第一时间联系本站管理员，经核实后我们会第一时间删除。
THE END
暂无评论内容