数据结构 链表(第7、8天)

简介: 数据结构 链表(第7、8天)

链表

这里面的链表题比较简单,只要会遍历链表、删除链表节点、反转链表这些基本操作就行。

必要时可以画图辅助理解。

141.环形链表

给定一个链表,判断是否有环。

思路:快慢指针。 快指针每次走两步,慢指针每次走一步。

如果某个时刻两个指针相遇,说明有环。

原理可以看官方题解,简单来说就是如果存在一个环,那么快指针和慢指针一定会掉到环里,在这个环里跑步,一快一慢总是会相遇的。

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

21. 合并两个有序链表

这个没啥好说的,就是遍历一下。

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        if  list2 is None:
            return list1
        elif list1 is None:
            return list2

        cur = dummy

        while list1 is not None and list2 is not None:
            if (list1.val <= list2.val):
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next

        if list1 is not None:
            cur.next = list1
        elif list2 is not None:
            cur.next = list2

        return dummy.next

203. 移除链表元素

删除所有值=val的节点。

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return head
        dm = ListNode(0,head)
        tm = dm
        while tm.next:
            if tm.next.val == val:
                tm.next = tm.next.next
            else:
                tm = tm.next
        return dm.next

206. 反转链表

反转链表,利用递归方法比较容易。

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

        res = self.reverseList(head.next) #剩下的
        head.next = None #断开第一个
        t = res
        while  t.next != None:
            t = t.next
        t.next = head #剩下的+第一个
        return  res

83. 删除排序链表中重复元素

注意是排序链表,所以重复元素一定相邻。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        h = head
        
        while head.next:
            if head.val == head.next.val:
                head.next = head.next.next
            else:
                head = head.next
                

        return h
相关文章
|
5天前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
24 8
【数据结构OJ题】合并两个有序链表
|
6天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
12 2
【数据结构OJ题】移除链表元素
|
6天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
9 1
【数据结构OJ题】链表中倒数第k个结点
|
6天前
|
存储 DataX C语言
【数据结构】双链表
数据结构中的双链表
14 1
【数据结构】双链表
|
4天前
【数据结构OJ题】链表分割
牛客题目——链表分割
5 0
【数据结构OJ题】链表分割
|
4天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
7 0
【数据结构OJ题】链表的回文结构
|
6天前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
9 0
【数据结构OJ题】链表的中间结点
|
6天前
【数据结构OJ题】反转链表
力扣题目——反转链表
10 0
【数据结构OJ题】反转链表
|
19天前
|
算法 Java
Java数据结构与算法:双向链表
Java数据结构与算法:双向链表
|
19天前
|
算法 Java
Java数据结构与算法:循环链表
Java数据结构与算法:循环链表