代码随想录Day03 | 链表基础1 LeetCode T203 移除链表元素 T707设计链表 T206 反转链表

本题思路和解答主要来源于:

代码随想录 (programmercarl.com)

LeetCode T203 移除链表元素

题目链接:203. 移除链表元素 - 力扣（LeetCode）

首先我们回顾一下单向链表,每个链表有一个指针域和一个数据域,在内存中是呈现不连续排列的,对比之前的数组,链表的查找的O(n)的是时间复杂度,因为链表需要一个一个的从头向后找,数组则是O(1)的时间复杂度,对于增添和删除元素,链表则只需要将待删除元素的前一个元素的指针指向后一个元素,是O(1)的时间复杂度,而对于数组则需要移动后面若干个元素,是O(n)的时间复杂度.

综上,我们得到了一条结论,在需要频繁查找而不需要频繁添加元素的集合里使用数组,反之使用链表.

思路1: 直接删除元素

这里有两个经典的思路,一是分头节点和后面的节点来讨论,我们先说这种思路,首先处理头节点的val是我们查找的val,我们一定是使用while循环而不是if语句,因为这个查找是持续进行下去的,如果我的链表是1->1->1->1,且查找值也是1的话那么只有一个if语句就不能解决问题.

注:一定要记得判断节点不为空
while (head != null && head.val == val) {head = head.next;}
然后我们判断一下头结点是否为空,如果是,直接返回头结点,不是我们就继续往后走,注意,我们要定义两个指针来解决移除元素的工作,一个pre指针是记录当前指针的前一个节点,cur指针是临时创建出来保证head不被修改的,然后我们判断只要cur指针是否为空,如果不是空指针且值相等我们就进行移除操作,不是空指针且值不等我们就进行前进操作.最后返回head即可.

完整实现代码:

while (head != null && head.val == val) {head = head.next;}if (head == null) {return head;}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;

思路2:使用虚拟头结点

这里我们还可以使用虚拟头结点,目的是统一移除操作,避免了额外来处理我们的头结点,我们也可以认为是常说的哨兵节点,这样我们可以统一从头结点出发,首先判断空链表,如果是就直接返回头节点,下面我们创建虚拟头结点dummy,让它的next指向头结点,创建一个cur节点指向head,pre指向dummy,只要cur不是空指针,我们就开始判断值,后面的操作同上,最后返回dummy的下一个节点.

实现代码

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;
}

LeetCode T707: 设计链表

链接:707. 设计链表 - 力扣（LeetCode）

其实就是设计链表的增删查的一些基础接口,这里我们仍然延续上文的虚拟头节点方式进行书写代码.我们一个功能一个功能来实现.

1. 定义单链表

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

2.初始化链表

初始化之前,我们先定义两个变量:链表长度,链表的虚拟头结点.
 int size;ListNode dummyHead;

public MyLinkedList() {size = 0;dummyHead = new ListNode(0) ;     }

3.获取index下标的元素

首先,判定index的合法性,如果index>size-1,那么直接返回-1,然后定义cur指针,指向虚拟头结点dummyHead,进行index+1次循环,找到目标元素,返回他的数据.至于为什么是index+1次,这里我们考虑极端情况,index = 0,这里我们需要进行一次循环,即cur = cur.next;

public int get(int index) {if(index>size-1){return -1;}ListNode cur = dummyHead;for(int i = 0;i<=index;i++){cur = cur.next;}return cur.val;}

4.在链表中间插入元素

因为题目要求有在链表末尾和头部插入元素,这里我们先实现在链表中间插入元素,后面前两个需求就迎刃而解了.

这里我们想再节点a和节点b中间加上一个节点c一定不能先让a节点的指针指向c节点,这样我们的b节点就找不到了,所以要让c节点先指向b节点,再用a节点指向c节点.

public void addAtIndex(int index, int val) {if(index>size){return;}size++;ListNode pre = dummyHead;for(int i = 0;i<index;i++){pre = pre.next;}ListNode toAdd = new ListNode(val);toAdd.next = pre.next;pre.next = toAdd;}

LeetCode T206 反转链表

链接:206. 反转链表 - 力扣（LeetCode）

思路1:双指针写法

实质上我们就是让这个链表的指针对调一个方向

这里我们prev就是最后尾指针指向的NULL,所以初始化为NULL,这里temp是为了保存cur指针的下一个元素,不然在cur指针反转后变成尾指针之后就找不到cur原本指向的元素了. ,然后循环的终止条件就是cur不等于空指针,因为原来的尾节点指向空指针,当cur等于空指针的时候,prev就是我们所求的反转后的头指针.

// 双指针
class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;ListNode cur = head;ListNode temp = null;while (cur != null) {temp = cur.next;// 保存下一个节点cur.next = prev;prev = cur;cur = temp;}return prev;}
}

思路2: 递归写法

递归写法实际上是双指针写法的一种延伸

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);}
}