leetcode探索初级算法之链表

1. 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

# 删除链表中的节点
# 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。


# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def deleteNode(self, node):
        # 题目给的是删除节点，那说明这个节点可以舍弃了，我们把下一个节点的值拷贝给当前要删除的节点，再删除下一个节点。
        node.val = node.next.val
        node.next = node.next.next

2. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

# 删除链表的倒数第N个节点
# 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。


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

class Solution:
    def removeNthFromEnd(self, head, n: int):
        # 设置两个指针，一快一慢
        # 快的指针先遍历到n个节点，然后慢的指针再跟着快指针一起遍历
        # 当快指针遍历完成时，就说明已经查找到了要删除掉的节点
        node = ListNode(0)
        node.next = head
        fast = node
        while n:
            fast = fast.next
            n -= 1
        slow = node
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return node.next

3. 反转链表

反转一个单链表。

# 反转链表
# 反转一个单链表。


# 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:
        if head is None:
            return None
        if head.next is None:
            return head
        # 从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)
        p = head.next
        while p.next is not None:
            q = p.next
            p.next = q.next
            q.next = head.next
            head.next = q
        # 之后，最后将第一个节点挪到新表的表尾。
        p.next = head
        head = p.next.next
        p.next.next = None
        return head

4. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

# 合并两个有序链表
# 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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


class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:  # 若当前l1数值小于l2，更新l1的下一节点，返回l1当前值
            l1.next = self.mergeTwoLists(l1.next, l2)  # 先将原l1.next传入进行递归比较，得到的值用来更新l1.next
            return l1
        else:  # 若当前l1数值大于等于l2，更新l2的下一节点，返回l2当前值
            l2.next = self.mergeTwoLists(l1, l2.next)  # 先将原l2.next传入进行递归比较，得到的值用来更新l2.next
            return l2

5. 回文链表

请判断一个链表是否为回文链表。

# 回文链表
# 请判断一个链表是否为回文链表。


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


class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True
        tmp = []
        pre = head
        while pre.next:
            tmp.append(pre.val)
            pre = pre.next
        tmp.append(pre.val)
        return tmp == tmp[::-1]

6. 环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

# 环形链表
# 给定一个链表，判断链表中是否有环。
#
# 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。


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


class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return False

        first = second = head
        while second and second.next:
            first = first.next
            second = second.next.next
            if first == second:
                return True
        return False