leetcode 2.两数相加
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
if not l1: return l2
if not l2: return l1
head = ListNode(-1)
pre = head
flag = 0
while l1 or l2:
tmp = flag
if l1: tmp += l1.val; l1 = l1.next
if l2: tmp += l2.val; l2 = l2.next
flag = tmp/10
pre.next = ListNode(tmp%10)
pre = pre.next
if flag: pre.next = ListNode(flag)
return head.next
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def removeNthFromEnd(self, head, n):
if not head or not n: return head
pre = ListNode(-1)
pre.next = head
slow = fast = pre
while n:
fast = fast.next
n -= 1
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return pre.next
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
# 递归
if not l1: return l2
if not l2: return l1
if l1.val<l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
# 迭代
if not l1: return l2
if not l2: return l1
pre = ListNode(-1)
first = pre
while l1 and l2:
if l1.val<l2.val:
pre.next = l1
l1 = l1.next
else:
pre.next = l2
l2 = l2.next
pre = pre.next
if l1: pre.next = l1
if l2: pre.next = l2
return first.next
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def mergeKLists(self, lists):
if not lists: return
n = len(lists)
return self.merge(lists, 0, n-1)
def merge(self, lists, left, right):
if left == right:
return lists[left]
mid = left + (right-left)//2
l1 = self.merge(lists, left, mid)
l2 = self.merge(lists, mid+1, right)
return self.mergeTwoLists(l1, l2)
def mergeTwoLists(self, l1, l2):
if not l1: return l2
if not l2: return l1
if l1.val<l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def swapPairs(self, head):
if not head or not head.next: return head
pre = ListNode(-1)
pre.next = head
swap_head.next = pre
while head and head.next:
p1 = head
p2 = head.next
swap_head = p2
p1.next = p2.next
p2.next = p1
swap_head = head
head = head.next
return pre.next
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseKGroup(self, head, k):
dummy = ListNode(-1)
dummy.next = head
pre = dummy
tail = dummy
while True:
count = k
while count and tail:
count -= 1
tail = tail.next
if not tail: break
head = pre.next
while pre.next!=tail:
cur = pre.next
pre.next = cur.next
cur.next = tail.next
tail.next = cur
pre = head
tail = head
return dummy.next
leetcode 61.旋转链表
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def rotateRight(self, head, k):
if not head or not head.next or not k: return head
# 合并成环
n = 1
tail = head
while tail.next:
tail = tail.next
n += 1
tail.next = head
# 寻找新的头尾
new_tail = head
for _ in range(n-k%n-1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteDuplicates(self, head):
# 保留一个重复元素
if not head or not head.next: return head
pre = head
while pre.next:
if pre.val == pre.next.val:
pre.next = pre.next.next
else:
pre = pre.next
return head
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def deleteDuplicates(self, head):
# 不保留重复元素
if not head or not head.next: return head
dummy = ListNode(-1)
dummy.next = head
pre = dummy
cur = pre.next
while cur and cur.next:
if cur.val==cur.next.val:
while cur.next and cur.val==cur.next.val:
cur = cur.next
pre.next = cur.next
cur = cur.next
else:
pre = pre.next
cur = cur.next
return dummy.next
leetcode 86.分隔链表
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def partition(self, head, x):
if not head or not head.next: return head
dummy1 = ListNode(-1)
dummy2 = ListNode(-1)
p1 = dummy1
p2 = dummy2
while head:
if head.val<x:
p1.next = head
p1 = p1.next
else:
p2.next = head
p2 = p2.next
head = head.next
p1.next = dummy2.next
p2.next = None
return dummy1.next
leetcode 206.反转链表
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseList(self, head):
if not head or not head.next: return head
pre = None
while head:
tmp = head.next
head.next = pre
pre = head
head = tmp
return pre
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
# 方法一: 找到要反转部分的链表,将其翻转,再与原链表拼接
def reverseBetween(self, head, m, n):
if not head or not head.next: return head
dummy = ListNode(-1)
dummy.next = head
pre = dummy
# 找到开始反转的前一个节点
for _ in range(m-1): pre = pre.next
# 反转链表
cur = pre.next
node = None
for _ in range(n-m+1):
tmp = cur.next
cur.next = node
node = cur
cur = tmp
# 连接反转前后的链表
pre.next.next = cur
pre.next = node
return dummy.next
# 方法二: 使用三个指针, 逐个向前插入需要反转节点
def reverseBetween(self, head, m, n):
if not head or not head.next: return head
dummy = ListNode(-1)
dummy.next = head
pre = dummy
# 找到开始反转的前一个节点
for _ in range(m-1): pre = pre.next
# 使用三个指针pre、start、tail, 不断将tail插入pre和pre.next
start = pre.next
tail = start.next
for _ in range(n-m):
start.next = tail.next
tail.next = pre.next
pre.next = tail
tail = start.next
return dummy.next
class Node:
def __init__(self, x, next=None, random=None):
self.val = int(x)
self.next = next
self.random = random
class Solution(object):
def copyRandomList(self, head):
if not head: return head
# 复制节点，将复制的节点插入到原来节点的后面
currentNode = head
while currentNode:
cloneNode = Node(currentNode.val, None, None)
nextNode = currentNode.next
currentNode.next = cloneNode
cloneNode.next = nextNode
currentNode = nextNode
# 为复制的节点添加随机指针
currentNode = head
while currentNode:
if currentNode.random:
currentNode.next.random = currentNode.random.next
currentNode = currentNode.next.next
# 拆分出复制的节点
currentNode = head
phead = currentNode.next
while currentNode:
cloneNode = currentNode.next
currentNode.next = cloneNode.next
if cloneNode.next:
cloneNode.next = cloneNode.next.next
currentNode = currentNode.next
return phead
leetcode 141.环形链表
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def hasCycle(self, head):
# 快慢指针
if not head: return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: return True
return False
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def detectCycle(self, head):
# 头部到入口为a, 环长为b-快慢指针相遇时有f=2s、f=s+nb求解得到f=2nb,s=nb
# 从头走到链表入口的路程为 k=a+nb
# 那么可以知道从头部到入口恰好a, s在sf相遇点出发再走a恰好到入口
slow = head
fast = head
while True:
if not fast or not fast.next: return
slow = slow.next
fast = fast.next.next
if slow == fast: break
fast = head
while fast!=slow:
fast = fast.next
slow = slow.next
return slow
leetcode 143.重排链表
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 not head or not head.next: return head
# 找到中点-即开始交换的前一个节点
mid, fast = head, head
while fast.next and fast.next.next:
mid = mid.next
fast = fast.next.next
# 翻转后一部分
pre = None
cur = mid.next
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
mid.next = pre
# 循环将后半部分插入前半部分
p1 = head
p2 = mid.next
while p1!=mid:
mid.next = p2.next
p2.next = p1.next
p1.next = p2
p1 = p2.next
p2 = mid.next
return head
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def insertionSortList(self, head):
#先找个排头dummy, 然后依次取head节点与dummy比较,插入其中
if not head or not head.next: return head
dummy = ListNode(-1)
pre = dummy
cur = head
while cur:
while pre.next and pre.next.val<cur.val:
pre = pre.next
tmp = cur.next
cur.next = pre.next
pre.next = cur
pre = dummy
cur = tmp
return dummy.next
leetcode 160.相交链表
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
if not headA or not headB: return
p1 = headA
p2 = headB
while p1!=p2:
p1 = p1.next if p1 else headB
p2 = p2.next if p2 else headA
return p1