代码随想录算法训练营第三天｜203.移除链表元素、707.设计链表、206.反转链表
一. 链表理论基础
-
链表是通过指针链接成的一种链式结构,链表的每个节点都有两部分组成,一个是数据区一个是指针;最后一个节点指向空代表链表结束;
-
链表有只指向下一节点的单链表和双向指向节点的双链表
-
如果链表最后一个节点指向头节点的话就是环形链表,循环链表可以用来解决约瑟夫环问题。
-
链表与数组的区别
- 数组在c++中是连续的存储空间(java中非连续),链表是不连续的;
- 数组创建后不能改变长度,删除节点只能覆盖,插入节点只能创建新数组,访问数据只需要下标就可以;链表插入删除比较方便但是查找的话需要从头查找
- 链表的程序定义
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; }
}
二. 链表相关算法题
203.移除链表元素
这道题考察链表的删除操作,链表删除很简单就是找到将要删除的节点,把节点的前位节点指向后一位即可
另外java是不需要考虑删除后的内存清理交由JVM处理,C++最好做一下内存清理操作
最好是定义一个虚拟头节点接入链表头这样好操作,不用单独写一段头节点删除逻辑
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode newHead = new ListNode(1,head); //新建个虚拟头把当前头接入,用于删除头节点
ListNode current = newHead; //存储当前判断的节点,将当前节点只想新的头节点,下面就可以直接判断下一节点
while(current.next != null){ //每次判断当前节点的下一节点
if (current.next.val == val){
current.next = current.next.next; //如果命中逻辑删除将当前节点的下一节点指向下下节点,这里要注意命中的话不用后移指针,下轮循环判断新接入的节点即:下下节点
}else {
current = current.next; //没有命中指针后移
}
}
return newHead.next;
}
}
707.设计链表
- 操作链表时要注意循环终止条件
- 定义一个虚拟头链表会少很多头处理工作
class MyLinkedList {
//单链表-虚拟头
private int val;
private MyLinkedList next;
public MyLinkedList() {
}
public int get(int index) {
int current = 0;
MyLinkedList currentNode = this.next;
while (currentNode != null) {
if (current == index) {
return currentNode.val;
}
current++;
currentNode = currentNode.next;
}
return -1;
}
public void addAtHead(int val) {
// 虚拟头的下一个就是Head
MyLinkedList linkedList = new MyLinkedList();
linkedList.val = val;
linkedList.next = this.next;
this.next = linkedList;
}
public void addAtTail(int val) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.val = val;
MyLinkedList linkedList = this;
while (linkedList.next != null) {
linkedList = linkedList.next;
}
linkedList.next = myLinkedList;
}
public void addAtIndex(int index, int val) {
if (index < 0) {
this.addAtHead(val);
return;
}
int current = 0;
MyLinkedList currentNode = this;
while (currentNode != null) {
if (current == index) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.val = val;
myLinkedList.next = currentNode.next;
currentNode.next = myLinkedList;
return;
}
current++;
currentNode = currentNode.next;
}
}
public void deleteAtIndex(int index) {
int current = 0;
MyLinkedList currentNode = this;
while (currentNode.next != null) {
if (current == index) {
currentNode.next = currentNode.next.next;
return;
}
current++;
currentNode = currentNode.next;
}
}
}
206.反转链表
迭代
-
时间复杂度O(n)
-
空间复杂度O(1)
-
需要注意将上一次的头节点与新的头节点连接,其它就是正常断开重新连接的操作了
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head; //如果是空链表直接返回
}
ListNode current = head; //记录当前指针节点
ListNode newHead = head; //需要返回的新链表
while (current.next != null) { //当链表尾端终止
head = newHead; //记录上次循环的头节点,以便后续新翻转过来的头节点连接
newHead = current.next; //新的头节点
current.next = current.next.next; //当前节点指向下下节点
newHead.next = head; //新头节点连接旧头节点
}
return newHead;
}
}
双指针法–这个更好理解哎
- 看下面代码随想录总结的动图就好了
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head; //如果是空链表直接返回
}
//双指针
ListNode current = head; //记录当前指针节点
ListNode newHead = null; //需要返回的新链表
ListNode temp = head;
while (current != null) { //当链表尾端终止
temp = current.next; //记录当前节点的下一节点备用,等会要重新连回到current
current.next = newHead;
newHead = current;
current = temp;
}
return newHead;
}
}
递归
递归其实就是做了双指针交换的事情,如图
- 时间复杂度O(logn)
- 空间复杂度O(1)
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head; //如果是空链表直接返回
}
return reverse(null,head);
}
ListNode reverse(ListNode newHead, ListNode current){
if (current == null){
return newHead;
}
ListNode temp = current.next;
current.next = newHead;
return reverse(current,temp);
}
}