LeetCode203 移除鏈表元素、LeetCode707 設計鏈表、LeetCode206 反轉鏈表

代碼隨想錄算法訓練營第三天 | 203-移除鏈表元素、707-設計鏈表、206-反轉鏈表

LeetCode203 移除鏈表元素

題目鏈接：https://leetcode.cn/problems/remove-linked-list-elements/description/

引入虛擬頭節點，這樣可以使用一套規則去刪除鏈表中節點，處理起來更加方便

如果是C++還得額外考慮內存回收，但我用的是Java，虛擬機自動回收內存hh

代碼隨想錄算法訓練營第三天｜ 203.移除鏈表元素、 707.設計鏈表、206.反轉鏈表_鏈表

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0,head);
        ListNode p = dummyHead;
        while(p.next != null){
            if(p.next.val == val){
                p.next = p.next.next;
            }else{
                p = p.next;
            }
        }

        return dummyHead.next;
    }
}

LeetCode707 設計鏈表

題目鏈接：https://leetcode.cn/problems/design-linked-list/description/

做這種涉及到指針的題目，要時刻明確當前狀態下指針到了什麼位置，注意細節和合法範圍條件，小心在一些細小的地方出錯（比如>和>=）

class MyLinkedList {

    class Node{
        int val;
        Node next;
        public Node(){}
        public Node(int val, Node next){
            this.val = val;
            this.next = next;
        }
    }

    Node dummyHead;
    int size;

    public MyLinkedList() {
        size = 0;
        dummyHead = new Node(0, null);
    }
    
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }

        Node cur = dummyHead;
        for(int i = 0;i <= index;i++){
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        Node newNode = new Node(val, dummyHead.next);
        dummyHead.next = newNode;
        size++;
    }
    
    public void addAtTail(int val) {
        Node cur = dummyHead;
        while(cur.next != null){
            cur = cur.next;
        }
        Node newNode = new Node(val, null);
        cur.next = newNode;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index < 0 || index > size){
            return;
        }

        Node cur = dummyHead;
        Node pre = null;
        for(int i = 0;i <= index;i++){
            pre = cur;
            cur = cur.next;
        }
        Node newNode = new Node(val, cur);
        pre.next = newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }

        Node cur = dummyHead;
        Node pre = null;
        for(int i = 0;i <= index;i++){
            pre = cur;
            cur = cur.next;
        }

        pre.next = cur.next;
        size--;
    }
}

LeetCode206 反轉鏈表

題目鏈接：https://leetcode.cn/problems/reverse-linked-list/description/

文章講解：https://programmercarl.com/0206.翻轉鏈表.html

視頻講解：https://www.bilibili.com/video/BV1nB4y1i7eL/?vd_source=b989f2b109eb3b17e8178154a7de7a51

採用雙指針的思路，cur指向當前節點，pre指向上一個節點，temp指向下一個節點，仔細畫畫圖分析遍歷過程，還是很清晰的

代碼隨想錄算法訓練營第三天｜ 203.移除鏈表元素、 707.設計鏈表、206.反轉鏈表_鏈表_02

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;

        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }

        return pre;
    }
}

依照雙指針解法的思路，還可以使用遞歸解決此問題：

代碼隨想錄算法訓練營第三天｜ 203.移除鏈表元素、 707.設計鏈表、206.反轉鏈表_i++_03

class Solution {
    public ListNode reverse(ListNode cur, ListNode pre){
        if(cur == null){
            return pre;
        }
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(temp, cur);
    }

    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
}