链表的结构
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
链表的题不难，多在于考察对链表操作的熟练度，问题常常在于链表是单向的，需要对链表的删除、反转、获取第n位的值等操作非常熟悉。
206. Reverse Linked List（Easy）
首先是最为经典的反转链表，很多题可以把反转的这一段代码直接拿出来当轮子用。
每次转换需要涉及到3个节点pre,cur,nex。
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre = None
while head:
nex = head.next
head.next,pre,head = pre,head,nex
return pre
2. Add Two Numbers（Medium）
非常常规的题，加法注意进位和l1、l2长度不一样的问题即可，开始我写的也对但比较复杂，下面的代码l1,l2,carry一个循环就搞定了。
def addTwoNumbers(self, l1, l2):
carry = 0 #进位
res = l3 = ListNode(0)
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
l3.next = ListNode(carry%10)
l3 = l3.next
carry //= 10
return res.next
19. Remove Nth Node From End of List（Medium）
删除链表的倒数第N位数（经典），令l1在前，l2先走n+1步，再让l1,l2循环到尾，此事倒数第n个数为l1.next。
def removeNthFromEnd(self, head, n):
res = l1 = l2 = ListNode(0)
res.next = head
for i in range(n+1): #l2先走n+1步
l2 = l2.next
while l2:
l1,l2 = l1.next,l2.next
l1.next = l1.next.next
return res.next
21. Merge Two Sorted Lists（Easy）
创建一个新的节点来保存合并后的节点比较方便。
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res = l3 = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
l3.next = l1
l1, l3 = l1.next, l3.next
else:
l3.next = l2
l2, l3 = l2.next, l3.next
l3.next = l1 or l2 #great solution
return res.next
24. Swap Nodes in Pairs（Medium）
保留前一个节点，每次交换下面的两个节点即可，该题注意一下一共用到三个节点即可。
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
res = pre = ListNode(0)
pre.next = head
while head and head.next:
l1,l2 = head,head.next
pre.next,l1.next,l2.next = l2,l2.next,l1
pre,head = l1,l1.next
return res.next
61. Rotate List（Medium）
这道题主要考察链表第n位获取操作，大于n取余数即可。
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if not head or not head.next:
return head
lenght = 1
start = head
while head.next:
lenght += 1
head = head.next
k = k % lenght
if k == 0:
return start
res = start
while res:
lenght -= 1
if lenght == k:
res.next,res = None,res.next
break
else:
res = res.next
head.next = start
return res
82. Remove Duplicates from Sorted List II（Medium）
保存好每个相同的节点的前一个节点，每次遇到相同的节点循环到不相同为止。
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
p = pre = ListNode(0)
p.next = head
tmp = head
while tmp and tmp.next:
if tmp.next.val == tmp.val:
while tmp.next and tmp.next.val == tmp.val:
tmp = tmp.next
tmp = tmp.next
pre.next = tmp
else:
pre = pre.next
tmp = tmp.next
return p.next
92. Reverse Linked List II（Medium）
反转链表 + 链表位移结合
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
res = ListNode(1)
res.next = head
pre = res
for i in range(1,m):
pre = pre.next
l1 = pre.next
l2 = l1.next
for i in range(n-m):
l2.next, l1, l2 = l1, l2, l2.next
pre.next.next = l2
pre.next = l1
return res.next
网友评论