代码随想录算法训练第三天
今日任务
- 链表理论基础
- 203.移除链表元素
- 707.设计链表
- 206.反转链表
链表理论基础
单向链表
双向链表
循环链表-链表首尾相连。循环链表可以用来解决约瑟夫环问题
链表节点
private class Node{
int val;
Node next;
public Node(int v){
this.val = v;
this.next = null;
}
public Node(int val, Node next){
this.val = val;
this.next = next;
}
}
链表操作
链表的插入与删除只需改变节点的next指针，复杂度均为O(1)。 链表的查询则需要通过next指针逐一遍历，复杂度为O(n)
与数组操作对比
| / | 插入/删除 | 查询 | 适应场景 |
|---|---|---|---|
| 链表 | O(1) | O(n) | 数量不固定，增删频繁，查询较少 |
| 数组 | O(n) | O(1) | 数量固定，查询频繁，增删较少 |
203. 移除链表元素
方法一： 递归
对于给定的链表，首先对除了头节点 head以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的val。如果 head 的节点值等于 val，则
head 需要被删除，因此删除操作后的头节点为 head.next；如果
head 的节点值不等于 val，则 head 保留，因此删除操作后的头节点还是
head。上述过程是一个递归的过程。
递归的终止条件是
head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
class Solution {
public ListNode removeElements(ListNode head, int val) {
//recursive
if(head == null) return head;
head.next = removeElements(head.next, val);
return head.val == val? head.next : head;
}
}
复杂度分析
time： O(n) 遍历链表一次
space: O(n) 用到递归栈，最多不超过n
方法二： 迭代
移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
可以设置一个虚拟头结点 dummyNode，这样原链表的所有节点就都可以按照统一的方式进行移除了。最后返回的时候记得返回 dummyNode.next 才是原来的头结点
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyNode = new ListNode(0);
ListNode curr = dummyNode;
dummyNode.next = head;
while(curr.next != null){
if(curr.next.val == val){
curr.next = curr.next.next;
}else{
curr = curr.next;
}
}
return dummyNode.next;
}
}
或者设置一个prev 变量
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode prev = dummyHead;
ListNode curr = head;
while(curr != null){
if(curr.val == val){
prev.next = curr.next;
}else{
prev = curr;
}
curr = curr.next;
}
return dummyHead.next;
}
}
复杂度分析
time： O(n) 遍历链表一次
space: O(1)
707. 设计链表
Medium难度
- 单向链表实现
class MyLinkedList {
private int size; //链表元素的个数
private ListNode head; //虚拟头指针
private class ListNode{
int val;
ListNode next;
ListNode(int v){
this.val = v;
}
ListNode(int v, ListNode n){
this.val = v;
this.next = n;
}
}
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index >= size) return -1;
ListNode cur = head;
for(int i = 0; i <= index; i++){ ////包含一个虚拟头节点，所以查找第 index+1 个节点
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if(index > size) return;
index = Math.max(0, index); //if index < 0, insert left
ListNode prev = head;
ListNode toAdd = new ListNode(val);
for(int i = 0; i < index; i++){
prev = prev.next;
}
toAdd.next = prev.next;
prev.next = toAdd;
size++;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size) return;
ListNode prev = head;
for(int i = 0; i < index ; i++){
prev = prev.next;
}
prev.next = prev.next.next;
size--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
复杂度分析
初始化O(1)； get(index) 为 O(index)；addAtHead 为 O(1); addAtTail 为O(index)； deleteAtIndex 为O(n)
- 双向链表实现
class MyLinkedList {
private int size;
ListNode head, tail;
private class ListNode{
int val;
ListNode prev;
ListNode next;
ListNode(int val){
this.val = val;
}
}
public MyLinkedList() {
size = 0;
head = new ListNode(0);
tail = new ListNode(0);
head.next = tail;
tail.prev = head;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
if(index < 0 || index >= size) return -1;
ListNode cur;
if(index <= size/2){
cur = head;
//index position closer to head, start from head
for(int i = 0; i <= index; i++ ){
cur = cur.next;
}
}else{
//index position closer to tail, start from tail
cur = tail;
for(int i = 0; i < size - index; i++){
cur = cur.prev;
}
}
return cur.val;
}
public void addAtHead(int val) {
addAtIndex(0, val);
}
public void addAtTail(int val) {
addAtIndex(size, val);
}
public void addAtIndex(int index, int val) {
if (index > size) return;
index = Math.max(0, index);
ListNode pred, succ;
if(index <= size/2){
pred = head;
//index position closer to head, start from head
for(int i = 0; i < index; i++ ){
pred = pred.next;
}
succ = pred.next;
}else{
//index position closer to tail, start from tail
succ = tail;
for(int i = 0; i < size - index; i++){
succ = succ.prev;
}
pred = succ.prev;
}
ListNode nodeToAdd = new ListNode(val);
nodeToAdd.prev = pred;
nodeToAdd.next = succ;
pred.next = nodeToAdd;
succ.prev = nodeToAdd;
size++;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size) return;
ListNode pred, succ;
if(index <= size/2){
pred = head;
//index position closer to head, start from head
for(int i = 0; i < index; i++ ){
pred = pred.next;
}
succ = pred.next.next;
}else{
//index position closer to tail, start from tail
succ = tail;
for(int i = 0; i < size - index - 1; i++){ //注意边界
succ = succ.prev;
}
pred = succ.prev.prev;
}
pred.next = succ;
succ.prev = pred;
size--;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
208. 反转链表
链表操作建议画图辅助更直观
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
ListNode tempNext = null;
while(curr != null){
//reverse
tempNext = curr.next;
curr.next = prev;
//point to next position
prev = curr;
curr = tempNext;
}
//now curr point to null, return prev
return prev;
}
}
时间复杂度 O(n)
空间复杂度 O(1)
