刪除鏈表中的重復(fù)元素

給定一個(gè)已排序的鏈表的頭 head ， 刪除所有重復(fù)的元素，使每個(gè)元素只出現(xiàn)一次 。返回 已排序的鏈表 。

示例：

輸入：head = [1,1,2]
輸出：[1,2]

輸入：head = [1,1,2,3,3]
輸出：[1,2,3]

提示：

鏈表中節(jié)點(diǎn)數(shù)目在范圍 [0, 300] 內(nèi)
-100 <= Node.val <= 100
題目數(shù)據(jù)保證鏈表已經(jīng)按升序 排列

思路：題目的意思有點(diǎn)像數(shù)組中的set操作，只留下不同的數(shù)。因?yàn)殒湵硎桥判虻?，所以相同的元素?huì)聚集在一起，思路見(jiàn)代碼：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        res = ListNode(0, head)
        cur = res.next
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return res.next

刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例：

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

輸入：head = [1], n = 1
輸出：[]

輸入：head = [1,2], n = 1
輸出：[1]

提示：

鏈表中結(jié)點(diǎn)的數(shù)目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

思路：快慢指針。fast指針先走n個(gè)節(jié)點(diǎn)，然后slow從起點(diǎn)和fast一起走完全程，此時(shí)slow指向倒數(shù)第n+1的節(jié)點(diǎn)。只要斷開(kāi)與slow.next.next即可。代碼如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        fast, slow = dummy, dummy
        while n:
            fast = fast.next
            n -= 1
        while fast and fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

環(huán)形鏈表

給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，判斷鏈表中是否有環(huán)。如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤 next 指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù) pos來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。注意：pos不作為參數(shù)進(jìn)行傳遞 。僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

示例：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

提示：

鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 104]
-105 <= Node.val <= 105
pos 為 -1 或者鏈表中的一個(gè) 有效索引 。

思路：追擊問(wèn)題，fast指針每次走兩步，slow指針每次走一步，假設(shè)有環(huán)，那fast一定可以追上slow一圈，如果沒(méi)有環(huán)，那永遠(yuǎn)也追不上。代碼如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

反轉(zhuǎn)鏈表

定義一個(gè)函數(shù)，輸入一個(gè)鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)。

示例：

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

提示：

0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 5000

思路：詳情見(jiàn)代碼和代碼注釋

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            tmp = cur.next  # 暫時(shí)存儲(chǔ)后續(xù)節(jié)點(diǎn)cur.next
            cur.next = pre  # 修改當(dāng)前節(jié)點(diǎn)指向
            pre = cur # pre向后挪動(dòng)一位
            cur = tmp # cur先后挪動(dòng)一位

相交鏈表

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回 null 。圖示兩個(gè)鏈表在節(jié)點(diǎn) c1 開(kāi)始相交：

image

題目數(shù)據(jù) 保證 整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。注意，函數(shù)返回結(jié)果后，鏈表必須 保持其原始結(jié)構(gòu) 。自定義評(píng)測(cè)：評(píng)測(cè)系統(tǒng) 的輸入如下（你設(shè)計(jì)的程序 不適用 此輸入）：

intersectVal - 相交的起始節(jié)點(diǎn)的值。如果不存在相交節(jié)點(diǎn)，這一值為 0
listA - 第一個(gè)鏈表
listB - 第二個(gè)鏈表
skipA - 在 listA 中（從頭節(jié)點(diǎn)開(kāi)始）跳到交叉節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)
skipB - 在 listB 中（從頭節(jié)點(diǎn)開(kāi)始）跳到交叉節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)

示例：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB= [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開(kāi)始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。

思路：創(chuàng)建兩個(gè)指針，讓兩個(gè)指針的后續(xù)鏈表部分長(zhǎng)度相等，然后尋找相同節(jié)點(diǎn)，找到返回，沒(méi)找到就返回None。代碼如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        len_a, len_b = 0, 0
        cur_a, cur_b = headA, headB
        # 獲得鏈表a的長(zhǎng)度
        while cur_a:
            len_a += 1
            cur_a = cur_a.next
        # 獲得鏈表b的長(zhǎng)度
        while cur_b:
            len_b += 1
            cur_b = cur_b.next
        # 使cur_a處于較長(zhǎng)的鏈表的指針
        if len_a < len_b:
            cur_a, cur_b = headB, headA
        else:
            cur_a, cur_b = headA, headB
        # 獲得鏈表長(zhǎng)度差值
        gap = abs(len_a - len_b)
        # 使兩個(gè)鏈表剩余長(zhǎng)度相同
        while gap:
            cur_a = cur_a.next
            gap -= 1
        # 判斷鏈表是否相交
        while cur_a and cur_b:
            if cur_a == cur_b:
                return cur_a
            else:
                cur_a = cur_a.next
                cur_b = cur_b.next
        return None