3

数据结构与算法复习-02-链表

 2 years ago
source link: https://rivers-shall.github.io/2020/06/15/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E5%A4%8D%E4%B9%A0-02-%E9%93%BE%E8%A1%A8/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

本文是数据结构与算法复习的第二篇博文，复习

  • 链表的概念
  • 常见的链表类型和设计取舍
  • 链表的反转操作

链表的概念

链表可以定义为:

  • 拥有一个节点，该节点有两个属性
    • val，本节点的值
    • next，另一个链表

首先，这个定义是单链表的定义，但是双向链表也是类似的

其次，从这个定义可以看到，链表是可以递归定义的

常见的链表类型和设计取舍

比较常见的链表类型有

所谓的设计取舍主要是考虑:

  • 选择单链表还是双向链表？
  • 是否需要卫士节点(sentinel node)?

单链表与双向链表

双向链表与单链表的区别就在于

  • 单链表每个节点只有一个next指向额外的链表(也就是后继元素)
  • 双链表每个节点有两个属性指向额外的链表(也就是前驱和后继)

所以双向链表的使用更加灵活

对于单链表和双链表的选择，主要是考虑两点:

  • 空间，双链表由于多了一个属性，消耗空间更多
  • 时间，这里是指
    • 如果有访问前驱节点的需求，可以考虑
      • 如果需要访问的前驱结点是固定的，比如固定是前一个节点或者前两个节点
        • 就可以直接使用额外的一个节点指针进行存储

是否需要卫士节点

卫士节点就是指

对于任意的链表，都向其中添加一个无用的节点，使得链表不会是0节点的链表

是否需要卫士节点主要是看个人的使用习惯

  • 使用卫士节点可以在一定程度上规避空指针的问题
    • 毕竟链表中一定会有节点
  • 但是会多出一个节点的空间消耗，且编程逻辑和无卫士节点的编程逻辑不同(废话，当然不同)

链表的翻转操作

链表考的最多的就是翻转(淡然还有单链表的快排，不过那个可以留到排序的时候再说)

链表的翻转有两种实现:

其实就是逻辑烦了点，实在不行代码背下来

循环实现链表翻转

如下代码的关键在于循环的不变式

每次循环开始前,head指向的是还未反转的链表头，prev指向的是已经反转的链表头

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

递归实现链表翻转

以下代码的关键在于函数声明

reverseList(headA, headB)会将headA的链表反转，然后将headB的链表拼接到反转的headA链表后

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseList(head, null);
    }

private ListNode reverseList(ListNode headA, ListNode headB) {
        if (headA == null) {
            return headB;
        }
        ListNode next = headA.next;
        headA.next = headB;
        return reverseList(next, headA);
    }
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK