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

203.移除鏈表元素

原方法:

• head是指向頭節點的指針
• 先處理頭節點的特殊情況,再判斷鏈表為空,因為可能頭節點處理后為空了
• cur是一個指針,用來遍歷鏈表

class Solution {
    public ListNode removeElements(ListNode head, int val) {
       
        while(head != null && head.val == val){
            head = head.next;
        }

         if(head == null){
            return head;
        }

        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }
}

虛擬頭節點

• 加了虛擬頭節點就不用單獨處理別的情況了

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        
        ListNode dummy =new ListNode();
        dummy.next = head;

        ListNode cur = dummy;
        while(cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}

遞歸:分三步

• head代表當前節點,head.next代表下一個節點

• 如果后續鏈表已處理好的情況下,如何處理當前節點

• 基準問題(終止條件):空鏈表不需要移除元素

• 分析問題(最簡單情況):當節點指向的子鏈中沒有val值時,只用判斷自己,若自己不等于val則返回自己,否則返回head.next

/**
 * 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) {
        //遞歸方法
        //確定問題:刪除鏈表中的val值,返回新的頭節點

        //基準問題:空鏈表不需要移除元素
        if(head == null){
            return head;
        }

        //分析問題:當節點指向的子鏈中沒有val值時,只用判斷自己
        head.next = removeElements(head.next, val);
        if(head.val == val){
            return head.next;
        }else{
            return head;
        }
    }
}

707.設計鏈表

最痛苦的一集

• 注意合法條件,index插入時,index可以等于size,相當于尾插
• java不能用while(i--),不合法
• 記得更新size

class MyLinkedList {
        class ListNode{
            int val;
            ListNode next;
            ListNode(int val){
                this.val = val;
            }
        } 

         private int size = 0;
         private ListNode dummyhead;

    public MyLinkedList() {
        this.size = 0;
        this.dummyhead = new ListNode(0);
    }
    
    public int get(int index) {
        ListNode cur = dummyhead.next;
        if(index < 0 || index > size - 1){
            return -1;
        }else{
            for(int i = 0; i < index; i++){
                cur = cur.next;
            }
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = dummyhead.next;
        dummyhead.next = newNode;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode cur = dummyhead;
        ListNode newNode = new ListNode(val);
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = newNode;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index < 0 || index > size - 1){
            return;
        }
        ListNode cur = dummyhead;
        ListNode newNode = new ListNode(val);

       for(int i = 0; i < index; i++){
            cur = cur.next;
        }
        newNode.next = cur.next;
        cur.next = newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size - 1){
            return;
        }
        ListNode cur = dummyhead;
        for(int i = 0; i < index; i++){
            cur = cur.next;
        }
        cur.next = cur.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);
 */

206.反轉鏈表

雙指針法

• cur : 遍歷鏈表
• pre : 記錄cur前面節點地址
• temp : 記錄cur后面節點地址

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

遞歸法

• head代表當前節點,head.next代表下一個節點

• 確定問題 : 若后續鏈表反轉好的情況下,如何處理自己

• 基準問題(終止條件) : 當head == null,和head.next == null時不需要操作

• 分析問題 : 當前節點的后一個節點指向自己,當前節點指向null

class Solution {
    public ListNode reverseList(ListNode head) {
       if(head == null || head.next == null){
        return head;
       }

       ListNode newHead = reverseList(head.next);
       head.next.next = head;
       head.next = null;
       return newHead;
    }
}