删除有序链表中重复的元素

删除有序链表中重复的元素-I牛客题霸牛客网 (nowcoder.com)

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.

题解：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code
        if head == None:
            return head
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

注意：cur.val与cur，cur = ... 与 cur.next = ...

合并两个排序的链表

https://www.nowcoder.com/share/jump/7463733061691027632211

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

思路：
比大小合并两个链表。双指针。
步骤：
①分别讨论两个链表为空情况
②新建一个表头（伪头节点），cur = head 指针指向表头
while循环{
③cur.next 接小头（比p1，p2大小）
④下移p小，下移cur
}
⑤if p 找非空指针，cur.next 接上它
⑥返回值去表头 head.next

题解：

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        if pHead1 == None: 
            return pHead2
        if pHead2 == None:
            return pHead1
        head = ListNode(0)
        cur = head
        while pHead1 and pHead2:
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next
        if pHead1:
            cur.next = pHead1
        else:
            cur.next = pHead2
        return head.next

判断链表中是否有环

https://www.nowcoder.com/share/jump/7463733061691030344202

判断给定的链表中是否有环。如果有环则返回true，否则返回false。
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

题解1:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return bool布尔型
#
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        if not head:
            return False
        fast, slow = head, head
        while fast and slow:
            slow = slow.next
            # if slow == None:
                # return False
            if fast.next == None:
                return False
            fast = fast.next.next
            if fast == slow:
                return True
        return False

题解2：

class Solution:
    def hasCycle(self , head ):
        # write code here
        if not head:
            return head
        # 双指针  快慢指针
        slow = head
        fast = head
        while slow and fast:
            slow = slow.next
            if fast.next:
                fast = fast.next.next
            else:
                return False
            # 当双指针相遇 即表示指针有环
            if slow == fast:
                return True
        return False

注意：
不能判断完slow.next =! None 就不判断fast.next了（可以类比理解：一个y=x，一个是y=2x，y1+1 = y2在x=1以外的情形不成立了），在 fast.next = None 的情况下fast.next.next会报错。