單鏈表
problem2 兩數(shù)相加
給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)。其中摊唇，它們各自的位數(shù)是按照 逆序 的方式存儲的左医，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。
如果特姐，我們將這兩個數(shù)相加起來晶丘，則會返回一個新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 0 開頭浅浮。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807
# 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
"""
flag = 0
p = pre = ListNode(0)
while l1 or l2:
if l1 is None:
l1 = ListNode(0)
if l2 is None:
l2 = ListNode(0)
res = (l1.val + l2.val + flag) % 10
flag = (l1.val + l2.val +flag) // 10
p.next = ListNode(res)
p = p.next
#p.next = p = ListNode(val)
l1 = l1.next
l2 = l2.next
if (l1 is None) and (l2 is None) and flag:
p.next = ListNode(1)
return pre.next
21. 合并兩個有序鏈表
將兩個有序鏈表合并為一個新的有序鏈表并返回沫浆。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
用遞歸滚秩，比自己寫的迭代簡潔
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
83. 刪除排序鏈表中的重復(fù)元素
給定一個排序鏈表专执，刪除所有重復(fù)的元素，使得每個元素只出現(xiàn)一次叔遂。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3
ps:雖是刪除但不改變原鏈表而是返回刪除的鏈表
# 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
"""
p = head
if head is None or head.next is None:
return head
while head.next:
if head.val == head.next.val:
head.next = head.next.next
else:
head = head.next
# p = head.next
#p.next = head
return p
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head == None or head.next== None:
return head
p = head
while True:
if p.val == p.next.val:
p.next = p.next.next
else:
p = p.next
if p.next==None:
break
return head
203. 移除鏈表元素
刪除鏈表中等于給定值 val 的所有節(jié)點他炊。
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
p = ListNode(0)
p.next = head
pre =p
while p and p.next:
if p.next.val == val:
p.next = p.next.next
else:
p = p.next
return pre.next
237. 刪除鏈表中的節(jié)點
請編寫一個函數(shù)，使其可以刪除某個鏈表中給定的（非末尾）節(jié)點哩掺，你將只被給定要求被刪除的節(jié)點凿叠。
現(xiàn)有一個鏈表 -- head = [4,5,1,9]，它可以表示為:
示例 1:
輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節(jié)點嚼吞，那么在調(diào)用了你的函數(shù)之后盒件，該鏈表應(yīng)變?yōu)?4 -> 1 -> 9.
示例 2:
輸入: head = [4,5,1,9], node = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個節(jié)點，那么在調(diào)用了你的函數(shù)之后舱禽，該鏈表應(yīng)變?yōu)?4 -> 5 -> 9.
說明:
- 鏈表至少包含兩個節(jié)點炒刁。
- 鏈表中所有節(jié)點的值都是唯一的。
- 給定的節(jié)點為非末尾節(jié)點并且一定是鏈表中的一個有效節(jié)點誊稚。
- 不要從你的函數(shù)中返回任何結(jié)果翔始。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next
142. 環(huán)形鏈表 II
給定一個鏈表脖镀，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)狼电，則返回 null蜒灰。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）肩碟。 如果 pos 是 -1卷员，則在該鏈表中沒有環(huán)。
說明：不允許修改給定的鏈表腾务。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點削饵。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環(huán)岩瘦，其尾部連接到第一個節(jié)點未巫。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)。
進階：
你是否可以不用額外空間解決此題启昧？
# 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
"""
s = {None}
while head not in s:
s.add(head)
head = head.next
return head
設(shè)環(huán)的起始節(jié)點為 E，快慢指針從 head 出發(fā)密末，快指針速度為 2握爷，設(shè)相交節(jié)點為 X，head 到 E 的距離為 H严里，E 到 X 的距離為 D新啼，環(huán)的長度為 L，那么有：快指針走過的距離等于慢指針走過的距離加快指針多走的距離（多走了 n 圈的 L） 2(H + D) = H + D + nL刹碾，因此可以推出 H = nL - D燥撞，這意味著如果我們讓倆個慢指針一個從 head 出發(fā)，一個從 X 出發(fā)的話迷帜，他們一定會在節(jié)點 E 相遇
class Solution(object):
def detectCycle(self, head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow == fast:
break
else:
return None
while head is not slow:
head = head.next
slow = slow.next
return head
206. 反轉(zhuǎn)鏈表
反轉(zhuǎn)一個單鏈表物舒。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題戏锹？
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p, rev = head, None
while p:
rev, rev.next, p = p, rev, p.next
return rev
···
Definition for singly-linked list.
class ListNode(object):
def init(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur, rev = head, None
while cur:
p = rev
rev = cur
cur = cur.next
rev.next = p
return rev
···
160. 相交鏈表
編寫一個程序，找到兩個單鏈表相交的起始節(jié)點锦针。
注意：
如果兩個鏈表沒有交點荠察，返回 null.
在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)伞插。
可假定整個鏈表結(jié)構(gòu)中沒有循環(huán)割粮。
程序盡量滿足 O(n) 時間復(fù)雜度，且僅用 O(1) 內(nèi)存媚污。
圖掛了>_<
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
pA=headA
pB=headB
while pA!=pB:
if pA==None:
pA = headB
else:
pA = pA.next
if pB==None:
pB = headA
else:
pB = pB.next
return pA
目前的超綱知識：深拷貝备图，排序（算法面試卡片的鏈表模塊）
82. 刪除排序鏈表中的重復(fù)元素 II
給定一個排序鏈表，刪除所有含有重復(fù)數(shù)字的節(jié)點，只保留原始鏈表中 *沒有重復(fù)出現(xiàn) *的數(shù)字揽涮。
示例 1:
輸入: 1->2->3->3->4->4->5
輸出: 1->2->5
示例 2:
輸入: 1->1->1->2->3
輸出: 2->3
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = pre = ListNode(0)
dummy.next = head
while head and head.next:
if head.val == head.next.val:
while head and head.next and head.val == head.next.val:
head.next = head.next.next
head = head.next
pre.next = head
else:
head = head.next
pre = pre.next
return dummy.next
