本文共 3966 字，大约阅读时间需要 13 分钟。

推荐：82，66（java）

72(python)https://github.com/CBLBY/datawhale_algorithm_learning/blob/master/Task02.ipynb

理论部分

• 理解线性表的定义与操作。
• 实现顺序表。
• 实现单链表、循环链表、双向链表。

练习部分

一、 线性表相关定义

基础： 数据结构： 是指数据元素的集合及元素间的相互关系和构造方法。 逻辑结构： 元素之间的相互关系（前后关系）是数据的逻辑结构。与存储位置无关。 存储结构： 数据元素及元素之间关系的存储称为存储结构（或物理结构）（指数据的逻辑结构在计算机存储空间的存放形式。）

数据结构按照逻辑关系的不同分为线性结构和非线性结构两大类。

线性表（Linear List）： 一个线性表是n(n≥0)个元素的有限序列，通常表示为（a₁,a₂, …,a_n）。线性结构的特点是数据元素之间程序一种线性关系，即元素“一个接一个排列”。 补充： 线性表的存储结构分为顺序存储和链式存储。

顺序表： 利用顺序存储结构（即利用数组）实现的线性表。

链表（Linked list）: 利用指针方式实现的线性表称为链表（单链表、循环链表、双链表）。它不要求逻辑上相邻的数据元素在物理位置上也相邻，即：逻辑结构与物理结构可以相同也可以不相同。 单向链表（单链表）： 每个结点只含有一个链域（指针域）的链表。即：利用单链域的方式存储线性表的逻辑结构。 双向链表（双链表）： 每个结点含有两个链域（指针域）的链表，分别指出当前元素的直接前驱和直接后驱。即：利用双链域的方式存储线性表的逻辑结构。 循环链表： 是一种首尾相连的单链表。即：在单链表（或双链表）中，将尾结点的指针域改为指向pHead，就得到循环链表。

链表本身是一种无序的数据结构，元素的插入和删除不能保证顺序性。

有序链表： 分不分有序单链表，有序双链表？ 有序链表的有序指顺序还是指值的大小？

有序 通常是针对标准顺序来说的，而标准顺序比如我们自然数由小到大的顺序就是标准顺序。有序链表主要是值其存的值 从头结点开始 跟标准顺序一致 小的在前面 大的在后面。

有序是指链表中存的值，从头结点开始由小到大排序。

单链表和双链表的区分在指针域的个数上面，单链表只有一个指针域存储后继结点的指针，双链表有两个指针域一个存后继节点的指针，另一存前驱节点的指针。

1. 合并两个有序链表
   https://leetcode-cn.com/problems/merge-two-sorted-lists/
   将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
   示例：

输入：1->2->4, 1->3->4输出：1->1->2->3->4->4

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        #先考虑链表其中一个为空的情况        if not l1:            return l2        if not l2:            return l1        curNode1 = l1        curNode2 = l2        #先选出第一个节点        if curNode1.val < curNode2.val:            head = curNode1            curNode1 = curNode1.next        else:            head = curNode2            curNode2 = curNode2.next        cur = head        while curNode1 and curNode2:            if curNode1.val < curNode2.val:                cur.next = curNode1                curNode1 = curNode1.next            else:                cur.next = curNode2                curNode2 = curNode2.next            cur = cur.next        #一直循环到有一个链表先结束        #如果是链表1先结束，则拼上链表2剩余的那段        if not curNode1:            cur.next = curNode2        #如果是链表2先结束，则拼上链表1剩余的那段        else:            cur.next = curNode1        return head

2. 删除链表的倒数第N个节点
   https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
   给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
   示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.说明：给定的 n 保证是有效的。进阶：你能尝试使用一趟扫描实现吗？

疑问：为什么快的要比慢的快n个节点？

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

3. 旋转链表
   https://leetcode-cn.com/problems/rotate-list/
   给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。

示例 1:输入: 1->2->3->4->5->NULL, k = 2输出: 4->5->1->2->3->NULL解释:向右旋转 1 步: 5->1->2->3->4->NULL向右旋转 2 步: 4->5->1->2->3->NULL示例 2:输入: 0->1->2->NULL, k = 4输出: 2->0->1->NULL解释:向右旋转 1 步: 2->0->1->NULL向右旋转 2 步: 1->2->0->NULL向右旋转 3 步: 0->1->2->NULL向右旋转 4 步: 2->0->1->NULL

不懂了

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def rotateRight(self, head: ListNode, k: int) -> ListNode:        if head is None or head.next is None:            return head        fast = head        slow = head        p = head        newHead = None        count = 1        while p.next:            p = p.next            count += 1        # 看不懂了        k = k % count        while fast.next:            fast = fast.next            if k<=0:                slow = slow.next            k -= 1        fast.next = head        newHead = slow.next        slow.next = None        return newHead

转载地址：https://blog.csdn.net/z583706/article/details/103860072 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！