代碼隨想錄算法訓(xùn)練第三天
今日任務(wù)
- 鏈表理論基礎(chǔ)
- 203.移除鏈表元素
- 707.設(shè)計(jì)鏈表
- 206.反轉(zhuǎn)鏈表
鏈表理論基礎(chǔ)
單向鏈表
雙向鏈表
循環(huán)鏈表-鏈表首尾相連借笙。循環(huán)鏈表可以用來解決約瑟夫環(huán)問題
鏈表節(jié)點(diǎn)
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;
}
}
鏈表操作
鏈表的插入與刪除只需改變節(jié)點(diǎn)的next指針医舆，復(fù)雜度均為O(1)。 鏈表的查詢則需要通過next指針逐一遍歷，復(fù)雜度為O(n)
與數(shù)組操作對比
| / | 插入/刪除 | 查詢 | 適應(yīng)場景 |
|---|---|---|---|
| 鏈表 | O(1) | O(n) | 數(shù)量不固定，增刪頻繁，查詢較少 |
| 數(shù)組 | O(n) | O(1) | 數(shù)量固定萍诱，查詢頻繁，增刪較少 |
203. 移除鏈表元素
方法一： 遞歸
對于給定的鏈表污呼，首先對除了頭節(jié)點(diǎn) head以外的節(jié)點(diǎn)進(jìn)行刪除操作，然后判斷 head 的節(jié)點(diǎn)值是否等于給定的val包竹。如果 head 的節(jié)點(diǎn)值等于 val燕酷，則
head 需要被刪除，因此刪除操作后的頭節(jié)點(diǎn)為 head.next周瞎；如果
head 的節(jié)點(diǎn)值不等于 val苗缩，則 head 保留，因此刪除操作后的頭節(jié)點(diǎn)還是
head声诸。上述過程是一個(gè)遞歸的過程酱讶。
遞歸的終止條件是
head 為空，此時(shí)直接返回 head彼乌。當(dāng) head 不為空時(shí)泻肯，遞歸地進(jìn)行刪除操作渊迁，然后判斷 head 的節(jié)點(diǎn)值是否等于 val 并決定是否要?jiǎng)h除 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;
}
}
復(fù)雜度分析
time： O(n) 遍歷鏈表一次
space: O(n) 用到遞歸棧灶挟，最多不超過n
方法二： 迭代
移除頭結(jié)點(diǎn)和移除其他節(jié)點(diǎn)的操作是不一樣的琉朽，因?yàn)殒湵淼钠渌?jié)點(diǎn)都是通過前一個(gè)節(jié)點(diǎn)來移除當(dāng)前節(jié)點(diǎn)，而頭結(jié)點(diǎn)沒有前一個(gè)節(jié)點(diǎn)稚铣。
可以設(shè)置一個(gè)虛擬頭結(jié)點(diǎn) dummyNode箱叁，這樣原鏈表的所有節(jié)點(diǎn)就都可以按照統(tǒng)一的方式進(jìn)行移除了。最后返回的時(shí)候記得返回 dummyNode.next 才是原來的頭結(jié)點(diǎn)
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;
}
}
或者設(shè)置一個(gè)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;
}
}
復(fù)雜度分析
time： O(n) 遍歷鏈表一次
space: O(1)
707. 設(shè)計(jì)鏈表
Medium難度
- 單向鏈表實(shí)現(xiàn)
class MyLinkedList {
private int size; //鏈表元素的個(gè)數(shù)
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++){ ////包含一個(gè)虛擬頭節(jié)點(diǎn)惕医，所以查找第 index+1 個(gè)節(jié)點(diǎn)
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);
*/
復(fù)雜度分析
初始化O(1)耕漱； get(index) 為 O(index)；addAtHead 為 O(1); addAtTail 為O(index)抬伺； deleteAtIndex 為O(n)
- 雙向鏈表實(shí)現(xià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. 反轉(zhuǎn)鏈表
鏈表操作建議畫圖輔助更直觀
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;
}
}
時(shí)間復(fù)雜度 O(n)
空間復(fù)雜度 O(1)
