算法|移除链表节点、翻转链表、设计链表

一、203. 移除链表元素

题目连接：https://leetcode.cn/problems/remove-linked-list-elements/
思路：单链表要移除元素，需要知道删除元素的前一个节点，改变前一个元素的pre.next等于cur.next
思路一：通过添加虚拟头节点，遍历如果下一个节点=val，即pre.next == val, 则删除next节点，即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;
    }
}

思路二：不使用虚拟节点，先看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. 反转链表

题目连接：https://leetcode.cn/problems/reverse-linked-list/
思路一、迭代法，记录前一个指针pre、让当前的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;
    }
}

思路二、使用递归、递归到最后一个元素时，即head.next == null，递归回溯，修改当前节点的next.next = 当前节点，并且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. 设计链表

题目连接：https://leetcode.cn/problems/design-linked-list/
1、使用单链表,设计一个虚拟头结点、查找的时候要 <= index, 添加和删除要找到前一个节点即 < index
添加节点：newListNode.next = pre.next;
       pre.next = newListNode;
       size++;
删除节点：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、使用双链表,注意查找的时候当 index >= size / 2 从后面向前搜索;同理删除和添加也是，获取到index的前一个节点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--;
    }
}