算法|移除鏈表節(jié)點(diǎn)、翻轉(zhuǎn)鏈表、設(shè)計(jì)鏈表

一、203. 移除鏈表元素

題目連接：https://leetcode.cn/problems/remove-linked-list-elements/
思路：單鏈表要移除元素，需要知道刪除元素的前一個(gè)節(jié)點(diǎn)，改變前一個(gè)元素的pre.next等于cur.next
思路一：通過添加虛擬頭節(jié)點(diǎn)，遍歷如果下一個(gè)節(jié)點(diǎn)=val，即pre.next == val, 則刪除next節(jié)點(diǎn)，即pre.next=pre.next.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) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode pre = dummyHead; 
        while (pre.next != null) {
            if (pre.next.val == val) {
                pre.next = pre.next.next;
            } else {
                pre = pre.next;
            }
        }
        return dummyHead.next;
    }
}

思路二：不使用虛擬節(jié)點(diǎn)，先看head是否等于val，等于修改head為head.next，在通過pre.next.val 是否等于val 來是否移除元素

/**
 * 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) {
        while (head != null && head.val == val){
            head = head.next;
        }
        ListNode pre = head;
        while (pre != null && pre.next != null) {
            if (pre.next.val == val) {
                pre.next = pre.next.next;
            } else {
                pre = pre.next;
            }
        }
        return head;
    }
}

二、 206. 反轉(zhuǎn)鏈表

題目連接：https://leetcode.cn/problems/reverse-linked-list/
思路一、迭代法，記錄前一個(gè)指針pre、讓當(dāng)前的cur.next=pre,在這之前要下記錄下next,cur = 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 reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

思路二、使用遞歸、遞歸到最后一個(gè)元素時(shí)，即head.next == null，遞歸回溯，修改當(dāng)前節(jié)點(diǎn)的next.next = 當(dāng)前節(jié)點(diǎn)，并且head.next = null;

/**
 * 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 reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode listNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return listNode;
    }
}

思路三、使用棧模擬遞歸的過程

/**
 * 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 reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        while (cur != null && cur.next != null){
            stack.push(cur);
            cur = cur.next;
        }
        ListNode newHead = cur;
        while (!stack.isEmpty()){
            ListNode listNode = stack.pop();
            listNode.next = null;
            cur.next = listNode;
            cur = listNode;
        }
        return newHead;
    }
}

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

題目連接：https://leetcode.cn/problems/design-linked-list/
1、使用單鏈表,設(shè)計(jì)一個(gè)虛擬頭結(jié)點(diǎn)、查找的時(shí)候要 <= index, 添加和刪除要找到前一個(gè)節(jié)點(diǎn)即 < index
添加節(jié)點(diǎn)：newListNode.next = pre.next;
? ? ? ?pre.next = newListNode;
? ? ? ?size++;
刪除節(jié)點(diǎn)：pre.next = pre.next.next;
? ? ? ?size--;

class MyLinkedList {
    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(){}
        public ListNode(int val) {
            this.val = val;
        }
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    private ListNode dummy;
    int size = 0;
    public MyLinkedList() {
        dummy = new ListNode();
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        ListNode cur = dummy;
        for (int i = 0; i <= index; i++){
            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;
        if (index < 0) index = 0;
        ListNode pre = dummy;
        for (int i = 0; i < index; i++){
            pre = pre.next;
        }
        ListNode newListNode = new ListNode(val);
        newListNode.next = pre.next;
        pre.next = newListNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        ListNode pre = dummy;
        for (int i = 0; i < index; i++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
        size--;
     }
}

2、使用雙鏈表,注意查找的時(shí)候當(dāng) index >= size / 2 從后面向前搜索;同理刪除和添加也是，獲取到index的前一個(gè)節(jié)點(diǎn)pre.
查找操作：

if (index > size / 2) {
    ListNode cur = tail;
    for (int i = 0; i < size - index; i++) {
        cur = cur.prev;
    }
    return cur.val;
} else {
    ListNode cur = head;
    for (int i = 0; i <= index; i++) {
        cur = cur.next;
   }
  return cur.val;
}

添加操作：ListNode newListNode = new ListNode(val);
? ? ? ?newListNode.next = pre.next;
? ? ? ?pre.next.prev = newListNode;
? ? ? ?pre.next = newListNode;
? ? ? ?newListNode.prev = pre;
刪除操作：pre.next.next.prev = pre;
? ? ? ?pre.next = pre.next.next;

class MyLinkedList {
    public static class ListNode {
        public int val;
        public ListNode next;
        public ListNode prev;
        public ListNode(){}
        public ListNode(int val) {
            this(val, null);
        }
        public ListNode(int val, ListNode next){
            this(val, next, null);
        }

        public ListNode(int val, ListNode next, ListNode prev) {
            this.val = val;
            this.next = next;
            this.prev = prev;
        }
    }
    private ListNode head;
    private ListNode tail;
    int size = 0;
    public MyLinkedList() {
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.prev = head;
        size = 0;
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        if (index  > size / 2) {
            ListNode cur = tail;
            for (int i = 0; i < size - index; i++){
                cur = cur.prev;
            }
            return cur.val;
        } else {
            ListNode cur = head;
            for (int i = 0; i <= index; i++){
                cur = cur.next;
            }
            return cur.val;
        }
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        // addAtIndex(size, val);
        ListNode newListNode = new ListNode(val);
        tail.prev.next = newListNode;
        newListNode.prev = tail.prev;
        newListNode.next = tail;
        tail.prev = newListNode;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        // ListNode pre = head;
        // for (int i = 0; i < index; i++){
        //     pre = pre.next;
        // }
        if (index == size) {
            addAtTail(val);
            return;
        }
        ListNode pre = getListPreNode(index);
        ListNode newListNode = new ListNode(val);
        newListNode.next = pre.next;
        pre.next.prev = newListNode;
        pre.next = newListNode;
        newListNode.prev = pre;
        size++;
    }
    
    private ListNode getListPreNode(int index) {
        if (index < 0 || index >= size) return null;
        if (index >= size / 2) {
            ListNode pre = tail;
            for (int i = 0; i <= size - index; i++){
                pre = pre.prev;
            }
            return pre;
        } else {
            ListNode pre = head;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            return pre;
        }
    }
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        // ListNode pre = head;
        // for (int i = 0; i < index; i++){
        //     pre = pre.next;
        // }
        // pre.next.next.prev = pre;
        // pre.next = pre.next.next;
        ListNode pre = getListPreNode(index);
        pre.next.next.prev = pre;
        pre.next = pre.next.next;
        size--;
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容