beyond myself

0%

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

发表于 分类于 ，

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

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

链表的概念

链表可以定义为:

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

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

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

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

比较常见的链表类型有

  • 单链表
  • 双向链表

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

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

单链表与双向链表

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

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

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

如何选择

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

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

是否需要卫士节点

卫士节点就是指

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

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

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

链表的翻转操作

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

链表的翻转有两种实现:

  • 循环实现
  • 递归实现

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

循环实现链表翻转

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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链表后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
    }
}