本题思路和解答主要来源于:
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: 设计链表
其实就是设计链表的增删查的一些基础接口,这里我们仍然延续上文的虚拟头节点方式进行书写代码.我们一个功能一个功能来实现.
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 反转链表
思路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); } }
总结:
在进行循环分析的时候,一定要设置好足够的节点先保存待会会消失的节点,可以给一定的极端的例子来验证代码的可行性,考虑好空指针的判断和结束条件即可.
