代碼隨想錄算法訓(xùn)練營第三天| 203.移除鏈表元素 707.設(shè)計(jì)鏈表 206.反轉(zhuǎn)鏈表

203.移除鏈表元素

原方法:

  • head是指向頭節(jié)點(diǎn)的指針
  • 先處理頭節(jié)點(diǎn)的特殊情況,再判斷鏈表為空,因?yàn)榭赡茴^節(jié)點(diǎn)處理后為空了
  • cur是一個(gè)指針,用來遍歷鏈表
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;
    }
}

虛擬頭節(jié)點(diǎn)

  • 加了虛擬頭節(jié)點(diǎn)就不用單獨(dú)處理別的情況了
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代表當(dāng)前節(jié)點(diǎn),head.next代表下一個(gè)節(jié)點(diǎn)

  • 如果后續(xù)鏈表已處理好的情況下,如何處理當(dāng)前節(jié)點(diǎn)

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

  • 分析問題(最簡單情況):當(dāng)節(jié)點(diǎn)指向的子鏈中沒有val值時(shí),只用判斷自己,若自己不等于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值,返回新的頭節(jié)點(diǎn)

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

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

707.設(shè)計(jì)鏈表

最痛苦的一集

  • 注意合法條件,index插入時(shí),index可以等于size,相當(dāng)于尾插
  • 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.反轉(zhuǎn)鏈表

雙指針法

  • cur : 遍歷鏈表
  • pre : 記錄cur前面節(jié)點(diǎn)地址
  • temp : 記錄cur后面節(jié)點(diǎn)地址
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代表當(dāng)前節(jié)點(diǎn),head.next代表下一個(gè)節(jié)點(diǎn)

  • 確定問題 : 若后續(xù)鏈表反轉(zhuǎn)好的情況下,如何處理自己

  • 基準(zhǔn)問題(終止條件) : 當(dāng)head == null,和head.next == null時(shí)不需要操作

  • 分析問題 : 當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)指向自己,當(dāng)前節(jié)點(diǎn)指向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;
    }
}