代码随想录算法训练营day03 ｜ 203.移除链表元素、707.设计链表、206.反转链表

链表的类型

���下来说一下链表的几种类型:

#单链表

刚刚说的就是单链表。

#双链表

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

如图所示： 

#循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

#链表的存储方式

了解完链表的类型，再来说一说链表在内存中的存储方式。

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

如图所示：

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

#链表的定义

接下来说一说链表的定义。

链表节点的定义，很多同学在面试的时候都写不好。

这是因为平时在刷leetcode的时候，链表的节点都默认定义好了，直接用就行了，所以同学们都没有注意到链表的节点是如何定义的。

而在面试的时候，一旦要自己手写链表，就写的错漏百出。

这里我给出C/C++的定义链表节点方式，如下所示：

// 单链表struct ListNode {    int val;  // 节点上存储的元素    ListNode *next;  // 指向下一个节点的指针    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数};

有同学说了，我不定义构造函数行不行，答案是可以的，C++默认生成一个构造函数。

但是这个构造函数不会初始化任何成员变量，下面我来举两个例子：

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);

使用默认构造函数初始化节点：

ListNode* head = new ListNode();head->val = 5;

所以如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！

#链表的操作

#删除节点

删除D节点，如图所示：

只要将C节点的next指针 指向E节点就可以了。

那有同学说了，D节点不是依然存留在内存里么？只不过是没有在这个链表里而已。

是这样的，所以在C++里最好是再手动释放这个D节点，释放这块内存。

其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

#添加节点

如图所示：

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

Java：

public class ListNode {    // 结点的值    int val;    // 下一个结点    ListNode next;    // 节点的构造函数(无参)    public ListNode() {    }    // 节点的构造函数(有一个参数)    public ListNode(int val) {        this.val = val;    }    // 节点的构造函数(有两个参数)    public ListNode(int val, ListNode next) {        this.val = val;        this.next = next;    }}

203.移除链表元素

力扣题目链接(opens new window)

题意：删除链表中等于给定值 val 的所有节点。

示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2： 输入：head = [], val = 1 输出：[]

示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：

当然如果使用java ，python的话就不用手动管理内存了。

还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。

这种情况下的移除操作，就是让节点next指针直接指向下下一个节点就可以了，

那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

这里就涉及如下链表操作的两种方式：

• 直接使用原来的链表来进行删除操作。
• 设置一个虚拟头结点在进行删除操作。

  来看第一种操作：直接使用原来的链表来进行移除。

  移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

  所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

  依然别忘将原头结点从内存中删掉。 

  这样移除了一个头结点，是不是发现，在单链表中移除头结点 和 移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

  那么可不可以 以一种统一的逻辑来移除 链表的节点呢。

  其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

  来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

  这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。

  这样是不是就可以使用和移除链表其他节点的方式统一了呢？

  来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。

  最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点

   

  Java：

  /** * 添加虚节点方式 * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param val * @return */public ListNode removeElements(ListNode head, int val) {    if (head == null) {        return head;    }    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作    ListNode dummy = new ListNode(-1, head);    ListNode pre = dummy;    ListNode cur = head;    while (cur != null) {        if (cur.val == val) {            pre.next = cur.next;        } else {            pre = cur;        }        cur = cur.next;    }    return dummy.next;}/** * 不添加虚拟节点方式 * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param val * @return */public ListNode removeElements(ListNode head, int val) {    while (head != null && head.val == val) {        head = head.next;    }    // 已经为null，提前退出    if (head == null) {        return head;    }    // 已确定当前head.val != val    ListNode pre = head;    ListNode cur = head.next;    while (cur != null) {        if (cur.val == val) {            pre.next = cur.next;        } else {            pre = cur;        }        cur = cur.next;    }    return head;}/** * 不添加虚拟节点and pre Node方式 * 时间复杂度 O(n) * 空间复杂度 O(1) * @param head * @param val * @return */public ListNode removeElements(ListNode head, int val) {    while(head!=null && head.val==val){        head = head.next;    }    ListNode curr = head;    while(curr!=null){        while(curr.next!=null && curr.next.val == val){            curr.next = curr.next.next;        }        curr = curr.next;    }    return head;}

   

  707.设计链表

  力扣题目链接(opens new window)

  题意：

  在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

    这道题目设计链表的五个接口：

    • 获取链表第index个节点的数值
    • 在链表的最前面插入一个节点
    • 在链表的最后面插入一个节点
    • 在链表第index个节点前面插入一个节点
    • 删除链表的第index个节点

      可以说这五个接口，已经覆盖了链表的常见操作，是练习链表操作非常好的一道题目

      链表操作的两种方式：

      1. 直接使用原来的链表来进行操作。
      2. 设置一个虚拟头结点在进行操作。

      下面采用的设置一个虚拟头结点（这样更方便一些，大家看代码就会感受出来）。

       

      /*class ListNode {    int val;    ListNode next;    ListNode(){}    ListNode(int val) {        this.val=val;    }}*/class MyLinkedList {    //size存储链表元素的个数    int size;    //虚拟头结点    ListNode head;    public MyLinkedList() {        size = 0;        head = new ListNode(0);    }        public int get(int index) {        if(index = size)            return -1;        ListNode cur = head;        for(int i=0;isize)            return;        if (index = size) {            return;        }        size--;        if (index == 0) {            head = head.next;    return;        }        ListNode pred = head;        for (int i = 0; i  
       
       
      06.反转链表
       
      力扣题目链接(opens new window)
       
      题意：反转一个单链表。
       
      示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
       
      思路
       
      如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
       
      其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
         
      之前链表的头节点是元素1， 反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改变next指针的方向。
       
      那么接下来看一看是如何反转的呢？
       
      我们拿有示例中的链表来举例，如动画所示：（纠正：动画应该是先移动pre，在移动cur）
         
      首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
       
      然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
       
      为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
       
      接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
       
      最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
       
       
       
      /** * Definition for singly-linked list. * public 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 tmp = null;//临时储存cur.next；        ListNode pre = null;        ListNode cur = head;        while(cur!=null){            tmp = cur.next;            cur.next = pre;            pre = cur;            cur = tmp;        }        return pre;    }}
       
       
       
      递归法
       
      递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
       
      关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。
       
      具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。
       
      // 递归 class Solution {    public ListNode reverseList(ListNode head) {        return reverse(null, head);    }    private ListNode reverse(ListNode prev, ListNode cur) {        if (cur == null) {            return prev;        }        ListNode temp = null;        temp = cur.next;// 先保存下一个节点        cur.next = prev;// 反转        // 更新prev、cur位置        // prev = cur;        // cur = temp;        return reverse(cur, temp);    }}