文章目录
练习题
219 · 在排序链表中插入一个节点
在链表中插入一个节点。
写了一个，但是爆了一个错，不知道是什么错误
def insertNode(self, head, val):
# write your code here
node = ListNode(val)
res, prev = head, head
if not head: return node
elif not head.next:
if head.val > val:
node.next = head
return node
else:
head.next = node
return head
head = head.next
while head:
if head.val >= val:
prev.next = node
node.next = head
break
prev = prev.next
head = head.next
return res
下面是官方答案。。。。
class Solution:
# @param head, a ListNode
# @param val, an integer
# @return the head of new linked list
def insertNode(self, head, val):
# Write your code here
dummy = ListNode(0, head)
p = dummy
while p.next and p.next.val < val:
p = p.next
node = ListNode(val, p.next)
p.next = node
return dummy.next
用了p.next.val，点睛之笔。
452 · 删除链表中的元素
删除链表中等于给定值 val 的所有节点。
我还是不能考虑全面，还是在打补丁，这可绝对不行。
def removeElements(self, head, val):
# write your code here
if not head.next:
if head.val == val: return
else: return head
while head and head.val == val:
head = head.next
if not head: return
cur = head
while cur:
while cur.next and cur.next.val == val:
cur.next = cur.next.next
cur = cur.next
return head
官方答案：
def removeElements(self, head, val):
# write your code here
dummy = ListNode(-1, head)
p = dummy
while p.next:
if p.next.val == val:
p.next = p.next.next
else:
p = p.next
return dummy.next
511 · 交换链表当中两个节点
给你一个链表以及两个权值v1和v2，交换链表中权值为v1和v2的这两个节点。保证链表中节点权值各不相同，如果没有找到对应节点，那么什么也不用做。
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param head: a ListNode
@param v1: An integer
@param v2: An integer
@return: a new head of singly-linked list
"""
def swapNodes(self, head, v1, v2):
# write your code here
cur, pre = head, None
while cur:
if not pre and (cur.val == v1 or cur.val == v2):
pre = cur
if (cur.val == v1 or cur.val == v2) and cur.val != pre.val:
pre.val, cur.val = cur.val, pre.val
break
cur = cur.next
return head
官方答案，我觉得好复杂：
def swapNodes(self, head, v1, v2):
if head is None:
return None
dummy = ListNode(0)
dummy.next = head
prev1, prev2 = self.findPrevs(dummy, v1, v2)
if prev1 is None or prev2 is None:
return head
if prev1 == prev2:
return head
if prev1.next == prev2:
self.swapAdjcent(prev1)
elif prev2.next == prev1:
self.swapAdjcent(prev2)
else:
self.swapRemote(prev1, prev2)
return dummy.next
# head->...->prev1->v1->...->prev2->v2...
# return prev1 & prev2
def findPrevs(self, dummy, v1, v2):
prev1, prev2 = None, None
node = dummy
while node.next is not None:
if node.next.val == v1:
prev1 = node
if node.next.val == v2:
prev2 = node
node = node.next
return prev1, prev2
# dummy->head->..->prev->node1->node2->post...
# swap node1 & node2
def swapAdjcent(self, prev):
node1 = prev.next
node2 = node1.next
post = node2.next
prev.next = node2
node2.next = node1
node1.next = post
# dummy->head->..->prev1->node1->post1->...->prev2->node2->post2...
# swap node1 & node2
def swapRemote(self, prev1, prev2):
node1 = prev1.next
post1 = node1.next
node2 = prev2.next
post2 = node2.next
prev1.next = node2
node2.next = post1
prev2.next = node1
node1.next = post2
228 · 链表的中点
找链表的中点，并返回这个节点。
def middleNode(self, head):
# write your code here
if not head: return
count = -1
dummy = ListNode(0, head)
while head:
count += 1
head = head.next
head = dummy.next
for _ in range(count // 2):
head = head.next
return head
一个大佬的回答，关于思考题的答案：
def middleNode(self, head):
# write your code here
if not head:
return None
count = 0
middle = head
while head.next:
head = head.next
count += 1
if count % 2 == 0:
middle = middle.next
return middle
快慢指针的想法，快指针走2步，慢指针走1一步，当快指针走完的时候，慢指针刚好在中间。
170 · 旋转链表
给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数
class Solution:
"""
@param head: the List
@param k: rotate to the right k places
@return: the list after rotation
"""
def rotateRight(self, head, k):
# write your code here
if not head: return None
fast, slow = head, head
if not fast.next: return fast
# 计算除loop真实步长
cur = head
count = 0
while cur:
count += 1
cur = cur.next
k %= count
if k == 0: return head
for _ in range(k):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
res = slow.next
slow.next = None
fast.next = head
return res
官方答案，和我写的差不多：
class Solution:
# @param head: the list
# @param k: rotate to the right k places
# @return: the list after rotation
def rotateRight(self, head, k):
# write your code here
if head==None:
return head
curNode = head
size = 1
while curNode!=None:
size += 1
curNode = curNode.next
size -= 1
k = k%size
if k==0:
return head
len = 1
curNode = head
while len<size-k:
len += 1
curNode = curNode.next
newHead = curNode.next
curNode.next = None
curNode = newHead
while curNode.next!=None:
curNode = curNode.next
curNode.next = head
return newHead
99 · 重排链表
我想写一个反转链表，然后两边同时走指针，但是不知道为什么，反转链表总是益处。于是我先看下答案吧：
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes’ values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
先找到中点，然后把后半段倒过来，然后前后交替合并。
def reorderList(self, head):
# write your code here
if None == head or None == head.next:
return head
pfast = head
pslow = head
while pfast.next and pfast.next.next:
pfast = pfast.next.next
pslow = pslow.next
pfast = pslow.next
pslow.next = None
pnext = pfast.next
pfast.next = None
while pnext:
q = pnext.next
pnext.next = pfast
pfast = pnext
pnext = q
tail = head
while pfast:
pnext = pfast.next
pfast.next = tail.next
tail.next = pfast
tail = tail.next.next
pfast = pnext
return head