【算法训练营Day03】链表part1

链表基础理论

几个需要关注的知识点：

• 链表与数组的不同之处就在于：链表在内存中不一定是连续的，可以是离散存储的，他们之间通过指针进行连接。这也就决定了链表是不能随机查询的，只能通过指针顺藤摸瓜进行顺序查询。
• 在数组中删除和添加操作会影响到后续的所有元素，而链表是通过指针链接，我们在删除和添加的时候，是对指针所指元素进行修改。
• 数组的长度在初始化的时候就已经定下来了，而链表的长度是可以不固定的，因为其离散的存在于内存之中。
• 链表的增加、删除操作一般可以引入一个虚拟头节点完成，使逻辑更加简洁，可以无需考虑头节点的更新以及边界情况的处理。
  • 要是有虚拟头节点，头节点就固定为虚拟头节点的下一个节点，所有的插入和删除操作都能以统一的方式进行处理。

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. 移除链表元素

删除逻辑：

• 首先为链表增添一个虚拟头节点
• 然后从头节点开始遍历整个链表找到要删除的元素
• 执行删除逻辑必不可少的两个节点就是删除节点的前缀节点和后缀节点
• 然后通过指针的修改完成链表的删除操作

代码如下：

/*** 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 removeElements(ListNode head, int val) {ListNode virtualHead = new ListNode(-1,head);ListNode pointer = virtualHead;while(pointer != null && pointer.next != null) {if(pointer.next.val == val) {pointer.next = pointer.next.next;continue;}pointer = pointer.next;}return virtualHead.next;}
}

设计链表

设计链表：707. 设计链表

逻辑不是很难，主要是调试解决一些细枝末节的问题。重点主要是了解链表的删除、添加逻辑（在有头节点的情况下）

代码如下：

class MyLinkedList {int val;MyLinkedList next;int length;public MyLinkedList() {val = -1;next = null;length = 0;}public MyLinkedList(int val,MyLinkedList next) {this.val = val;this.next = next;}public int get(int index) {if(index >= length || index < 0) {return -1;}int count = index + 2;MyLinkedList pointer = this;while(count > 0) {if(count == 1) return pointer.val;count -= 1;pointer = pointer.next;}return -1;}public void addAtHead(int val) {MyLinkedList addNode = new MyLinkedList(val,this.next);this.next = addNode;length += 1;}public void addAtTail(int val) {MyLinkedList pointer = this;while(pointer.next != null) pointer = pointer.next;MyLinkedList addNode = new MyLinkedList(val,null);pointer.next = addNode;length += 1;}public void addAtIndex(int index, int val) {if(index > length || index < 0) {return;}else if(index == length) {addAtTail(val);}else if(index == 0){addAtHead(val);}else {int count = index + 1;MyLinkedList pointer = this;while(count > 0 && pointer.next != null) {if(count == 1) {MyLinkedList addNode = new MyLinkedList(val,pointer.next);pointer.next = addNode;}count -= 1;pointer = pointer.next;}length += 1;}}public void deleteAtIndex(int index) {if(index >= length || index < 0) {return;}else {int count = index + 1;MyLinkedList pointer = this;while(count > 0 && pointer.next != null) {if(count == 1) {pointer.next = pointer.next.next;}count -= 1;pointer = pointer.next;}length -= 1;}}
}

反转链表

题目链接：206. 反转链表

解题逻辑：在遍历链表的同时，使用头插法创建一个新链表，得到的新链表就是反转后的链表。

代码如下：

class Solution {public ListNode reverseList(ListNode head) {ListNode reverseResultVirtualHead = new ListNode();ListNode pointer = head;while(pointer != null) {ListNode currentNode = new ListNode(pointer.val,null);currentNode.next = reverseResultVirtualHead.next;reverseResultVirtualHead.next = currentNode;pointer = pointer.next;}return reverseResultVirtualHead.next;}
}