LeetCode 2

203. Remove Linked List Elements

注意：链表的定义很简单，只要创建一个ListNode类并实例化就算完成了，其中每个实例代表一个节点，因此每个实例都得有value和next，分别表示该节点的值和指向下一节点的指针：

class ListNode(object):
    def __init__(self, val=0, head=None):
            self.val = val
                self.next =  next

而遍历链表也不同于for循环，其主要通过头节点的指针不断寻找下一个节点，也就是current = current.next

例如创建一个链表并遍历：

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

current = head #从头开始遍历
while current.next:
    print(current.val)
        current = current.next # 指针指向现在的节点的下一个节点

知道这些后，删除节点这一题就好解决了：

逐步解释代码：

首先使用dummy head哨兵节点来指向head节点，防止要删除的节点是头节点

dummy_head = ListNode(0, head)
然后将哨兵节点和链表的头节点连接起来，然后再将指针指向现在的位置：

dummy_head.next = head
current = dummy_head

然后遍历链表

while current.next : # 如果next=none就说明到达链表尾部，停止循环
    if current.next.val == val:
            current.next = current.next.next
     else:
         current = current.next # 指针指向下一个节点

最后再返回链表的头节点就完事了，因为你可以通过头节点这个实例来逐步得到之后的节点

707. Design Linked List

class ListNode(object):
    def __init__(self, val=0, next=None, index=0):
        self.val = val
        self.next = next
        self.index = index # 没有必要index，直接通过for循环的次数和size就能确认位置

class MyLinkedList(object):

    def __init__(self):
        self.head = ListNode() # 直接self.head = None初始化即可，一开始是空而不需要其他东西
        self.dummy_head = ListNode(0, self.head, -1) # 完全不需要dummy，因为按照索引删除的时候如果删除了头节点也只需要将头节点的next指向下一个即可
        self.dummy_head.next = self.head
        self.size = 0 # 使用size来时刻记录链表长度

    def get(self, index): # 需要考虑index的合法性，主要体现在小于0和大于等于size以及size为0的情况
        """
        :type index: int
        :rtype: int
        """
        current = self.dummy_head.next # 直接让指针等于头节点即可
        while current.next: # 可以通过for _ in range(index)：来找到index位置的节点，并返回val
            if current.index == index:
                return current.val
            else:
                current = current.next

        return -1 


    def addAtHead(self, val): # 在头部添加新节点同样很简单，只需要创建一个新节点对象，然后将对象的next指向头节点就行了，注意size++
        """
        :type val: int
        :rtype: None
        """
        head = NodeList(val, self.head, 0)
        head = self.dummy_head.next
        head.next = self.head
        current = head
        i = 0
        while current.next:
            current = current.next
            i += 1
            current.index = i

        self.size += 1

    def addAtTail(self, val): # 在尾部添加则是通过size找到最后一个节点，然后创建一个新节点对象，让最后一个节点的next指向它，size++
        """                           
        :type val: int   #还得注意如果size是0，那就是添加头节点
        :rtype: None
        """
        current = self.dummy_head.next
        i = 0
        while current.next:
            current = current.next
            i += 1

        tail = NodeList(val, None, i)
        current.next = tail

        self.size += 1

上面的代码时直接写的代码，错误很多，关键思路已给出，接下来是其他没写的函数：

def addAtIndex(self, index, val):
    #首先还是判断index合法，如果不合法则return ，表示什么都不返回，注意这个时候可以等于size，表示在size这个位置新创建一个节点
        # 如果index为0，那就是添加头节点
        # 否则则和查找类似，遍历到index的前一个位置，然后创建新节点，将将它的next指向后一个节点，然后再前一个节点的next指向它，size++

def deleteAtIndex(self, index):
    #首先判断index是否合法
        # 如果index==0，那就是删除头节点，直接将头节点next指向的节点赋值给头节点就可以了self.head = self.head.next
        # 否则那就遍历到index的前一个节点，然后将后一个节点的next直接指向前一个节点的next就行了current.next = current.next.next。size--

206. Reverse Linked List

class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        current = head
        if current == None:
            return # 这里不能空，而是None
        elif current.next == None:
            return current

        else:
            dummy_head = ListNode(0, current)
            while current.next:
                current = current.next

            while current != head:
                current = current.next # 这里并不会反转链表
            return current

还是存在大量错误，问题的关键就是反转链表时需要使用一个中间变量tmp来储存current.next指向的节点，并且同时定义另一个指针prev用于新的表头。

双指针法，prev和current两个指针，并通过tmp来暂存中间值防止值丢失

tmp = current.next
current.next = prev 
prev = current # 将current本身作为current.next的prev指向的节点，而current.next则被上一轮的prev覆盖
current = tmp # current.next的值赋给current，实现反转

24. Swap Nodes in Pairs

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        current = head

        if current == None: # 首先不需要这样，直接判断head是否为none和head.next是否为none就可以知道链表节点数是否为2个以下
            return None
        if  current.next == None:
            return current
        if current.next.next ==None:
            tmp = current
            current = current.next
            current.next = tmp
            return current
        while current: # current 和 current.next都不为none才继续循环，保证有两个节点可以交换
            a = current.next.next
            prev = current
            current = current.next
            current.next = prev
            current.next.next = a
            current = current.next

        return current

还是有大量错误，节点交换的指针和顺序需要特别注意！！

 #关键是使用dummy head来指向头节点，这样方便非常多
        dummy_head = ListNode(0, head)
        current = head # 指针指向头节点
        prev = dummy_head # 头节点的prev指针指向其前一个节点，也就是dummy head。
        # 这两个指针是关键，current用于指向接下来要操作的pair，prev指向要操作的pair的前一个节点位置

while current and current.next:
        second = current.next #将第二个节点储存
        next_pair = current.next.next #将第三个节点，也就是下一个pair的开头节点储存

        # 开始交换，首先将第二个节点的next指向要交换的第一个节点
        second.next = current
        # 然后将第一个节点的next指向第三个节点
      current.next = next_pair
        # 最后将头节点前面的prev节点的next指向交换完成的头节点second
        prev.next = second

        # 上面的顺序应该是可以随便的，current和second由于交换位置所以current所指向的节点是第二个节点，second是第一个节点
        # 最后就是处理两个指针prev和current
        prev = current # 先将current所指向的节点，也就是第二个节点储存到prev，这样prev对应的节点就是next_pair的前一个节点
        current = next_pair # 将current指向下一组开始

        return dummy.next #最后再返回头节点

19. Remove Nth Node From End of List

算是自己做对的一题，关键思路是找到链表长度size，再通过size-n来将倒方向变为正方向

其中n取值不同分不同情况讨论，如果n取到头节点了就是head=head.next，其他情况就是遍历然后删除

并且head为none或者只有一个节点的时候情况也不同

复杂度为O(2n)

另一种解法：

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)  # 哨兵节点，防止删除头节点时出错
    first = second = dummy

    # 让 first 指针先前进 `n+1` 步，使 second 停在待删除节点的前一个
    for _ in range(n + 1):
        first = first.next

    # 让 first 和 second 同步前进，直到 first 到达 `None`
    while first:
        first = first.next
        second = second.next

    # 删除目标节点
    second.next = second.next.next

    return dummy.next  # 返回新的头节点

160. Intersection of Two Linked Lists

这题非常巧妙，主要有两种解法

1.双指针法：

思路：让两个指针 走完相同的路程，确保它们在相交点相遇，或者同时到达 None

headA: A1 → A2 → A3 → C1 → C2 → C3

headB: B1 → B2 → C1 → C2 → C3

A 链表的长度 = a + c，B 链表的长度 = b + c，c 是公共部分（相交部分）的长度

指针pA 先遍历 headA（长度 a + c），然后跳到 headB 继续走（长度 b）

指针pB 先遍历 headB（长度 b + c），然后跳到 headA 继续走（长度 a）

它们最终都走了 a + c + b 的距离，所以一定会相遇在交点 C1。

pA 走的路径： A1 → A2 → A3 → C1 → C2 → C3 → B1 → B2 → C1

pB 走的路径： B1 → B2 → C1 → C2 → C3 → A1 → A2 → A3 → C1

它们都在 C1 处相遇，所以 C1 就是交点。如果没有相交的情况下，pA 和 pB 最终都会变成 None，返回 None。

#核心代码
pA = headA
pB = headB
while pA != pB:
    if pA is None:
            pA = headB
     else:
         pA = pA.next

    if pB is None:
        pB = headA
 else:
     pB = pB.next

return pA

2.相同长度法

核心思想：两个链表可能长度不相等，因此找出长的链表，将指针指向和短的链表的长度相同的位置开始一起遍历，遍历到相同的val就返回，否则就返回None

def get_length(head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    lenA, lenB = get_length(headA), get_length(headB)

    while lenA > lenB:
        headA = headA.next
        lenA -= 1

    while lenB > lenA:
        headB = headB.next
        lenB -= 1

    while headA != headB:
        headA = headA.next
        headB = headB.next

    return headA

141. Linked List Cycle

判断是否有环，需要记住floyd算法

也就是快慢指针法，设fast指针每次走两步，slow指针每次走一步，如果快的指针还能和慢的相遇那就说明肯定有环

注意判断条件：

while fast and fast.next: # 不是while fast.next.next或者while fast.next

这是因为fast 不会是 None，避免 fast.next 访问错误。fast.next 也不会是 None，避免 fast.next.next 访问错误。

142. Linked List Cycle II

本题和141一样先通过floyd算法判断是否有环，有环的话再进一步寻找环的入口！

如果有环，此处需要数学推导

链表头到环入口的距离 a，快慢指针相遇点到环起点的距离 b，环的长度 c：

快指针走的步数 = a + b + k*c （k 表示完整绕环 k 圈）

慢指针走的步数 = a + b

慢指针先从head开始走到环口距离是a，再从环口走到相遇点的距离是b，同理，快指针先走了a后，先进入环内绕圈，绕了k圈后再到相遇点，也就是a+ k*c + b （此时 slow 在环中某个点，而 fast 走过的总路程比 slow 多整 k 圈。）

快指针走的步数是慢指针的两倍：2(a+b)=a+k∗c+b，也就是a=k∗c−b

等式左右相等说明：从 head 走 a 步，与 slow 从 b 位置开始继续走 都会到环的起点，所以它们一定会相遇！

也就是说a = c-b，我们使k等于1也能满足等式成立，也就是说从 head 走 a 步=slow走b-c步

if fast == slow:
    entry = head
    while entry != slow:
        entry = entry.next
        slow = slow.next
    return entry