链表LinkedList

设计链表

class MyLinkedList {

    /** Initialize your data structure here. */
    private int size;
    private Node head;
    private Node tail;

    class Node{
        private int val;
        private Node next;
        private Node prev;
        public Node(int val){
            this.val = val;
        }
    }
    public MyLinkedList() {
        this.size = 0;
        this.head = new Node(-1);
        this.tail = new Node(-1);
        head.next = tail;
        tail.prev = head;
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if(index < 0 || index > size - 1){
            return -1;
        }
        Node temp;
        if(index < (size >> 1)){
            temp = head;
            for(int i = 0; i < index + 1; i++){
                temp = temp.next;
            }
        }else{
            temp = tail;
            for(int i = 0; i < size - index; i++){
                temp = temp.prev;
            }
        }

        return temp.val;
    }
    
    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if(index < 0 || index > size){
            return;
        }
        Node pre, after;
        if(index < (size >> 1)){
            pre = head;
            for(int i = 0; i < index; i++){
                pre = pre.next;
            }
            after = pre.next;
        }else{
            after = tail;
            for(int i = 0; i < size - index; i++){
                after = after.prev;
            }
            pre = after.prev;
        }

        Node newNode = new Node(val);
        newNode.next = after;
        after.prev = newNode;
        pre.next = newNode;
        newNode.prev = pre;
        size++;
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size - 1){
            return;
        }
        Node pre, after;
        if(index < (size >> 1)){
            pre = head;
            for(int i = 0; i < index; i++){
                pre = pre.next;
            }
            after = pre.next.next;
        }else{
            after = tail;
            for(int i = 0; i < size - index - 1; i++){
                after = after.prev;
            }
            pre = after.prev.prev;
        }

        pre.next = after;
        after.prev = pre;
        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);
 */

环形链表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }

        return false;
    }
}

环形链表II

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                ListNode temp = head;
                while(temp != slow){
                    temp = temp.next;
                    slow = slow.next;
                }

                return temp;
            }
        }

        return null;
    }
}

相交链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while(A != B){
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }

        return A;
    }
}

删除链表的倒数第N个节点

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode slow = dummy, fast = head;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }

        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;

        return dummy.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) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = null, cur = head;
        while(cur != null){
            ListNode nextNode = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nextNode;
        }

        return pre;
    }
}

递归实现

/**
 * 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 newNode = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newNode;
    }
}

移除链表元素

/**
 * 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) {
        //边界条件
        if(head == null){
            return head;
        }

        //构建一个哨兵节点
        ListNode dummy = new ListNode(-1, head);
        ListNode temp = dummy;
        while(temp.next != null){
            //判断当前节点的下一个节点的值是否为val
            if(temp.next.val == val){
                //是则删除节点
                temp.next = temp.next.next;
            }else{
                //否就遍历下一节点
                temp = temp.next;
            }
        }

        return dummy.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 oddEvenList(ListNode head) {
        //边界条件
        if(head == null || head.next == null){
            return head;
        }
        //构建两个链表，基数的头节点为head，偶数的头节点为newNode
        ListNode temp = head, newNode = head.next, temp1 = newNode;
        while(temp1 != null && temp1.next != null){
            //把一号节点的下一个指向三号节点
            temp.next = temp1.next;
            //指向三号节点
            temp = temp.next;
            //把二号节点的下一指向四号节点
            temp1.next = temp.next;
            //指向四号节点
            temp1 = temp1.next;
        }
        //基数链表的尾部连接偶数链表
        temp.next = newNode;
        return head;
    }
}

回文链表

/**
 * 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 boolean isPalindrome(ListNode head) {
        //边界条件
        if(head == null || head.next == null){
            return true;
        }
        //定义快慢指针，并且反转前一半
        ListNode slow = head, fast = head, pre = null, cur = head;
        while(fast != null && fast.next != null){
            cur = slow;
            slow = slow.next;
            fast = fast.next.next;
            cur.next = pre;
            pre = cur;
        }
        if(fast != null){
            slow = slow.next;
        }
        //比较反转部分和原链表的后半部分
        while(cur != null && slow != null){
            if(cur.val != slow.val){
                return false;
            }
            cur = cur.next;
            slow = slow.next;
        }

        return true;
    }
}

合并两个有序链表

/**
 * 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 mergeTwoLists(ListNode l1, ListNode l2) {
        //边界条件
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

        //构建一个哨兵节点
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                temp.next = l1;
                l1 = l1.next;
            }else {
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }

        if(l1 == null){
            temp.next = l2;
        }
        if(l2 == null){
            temp.next = l1;
        }

        return dummy.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 addTwoNumbers(ListNode l1, ListNode l2) {
        //构建一个哨兵节点
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        //保留计算的进位值
        int sum = 0;
        while(l1 != null || l2 != null || sum != 0){
            if(l1 != null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2 != null){
                sum += l2.val;
                l2 = l2.next;
            }
            //构建新节点
            temp.next = new ListNode(sum%10);
            sum /= 10;
            temp = temp.next;
        }

        return dummy.next;
    }
}

扁平化多级双向链表

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        //边界条件
        if(head == null){
            return head;
        }

        //构建一个哨兵节点
        Node dummy = new Node(-1, null, head, null);

        dfs(dummy, head);
        dummy.next.prev = null;

        return dummy.next;
    }
    //深度优先搜索
    private Node dfs(Node prev, Node curr){
        //递归出口
        if(curr == null){
            return prev;
        }
        curr.prev = prev;
        prev.next = curr;

        //记录当前节点的右子树
        Node right = curr.next;
        //递归调用搜索左子树
        Node tail = dfs(curr, curr.child);
        curr.child = null;

        return dfs(tail, right);
    }
}

复制带随机指针的链表

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        //边界条件
        if(head == null){
            return head;
        }

        //复制节点
        Node temp = head;
        while(temp != null){
            Node newNode = new Node(temp.val);
            newNode.next = temp.next;
            temp.next = newNode;
            temp = newNode.next;
        }

        //复制random指针
        temp = head;
        while(temp != null){
            temp.next.random = temp.random == null ? null : temp.random.next;
            temp = temp.next.next;
        }

        //拆开两个链表
        Node oldNode = head;
        Node newNode = head.next;
        Node res = head.next;
        while(oldNode != null){
            oldNode.next = oldNode.next.next;
            newNode.next = newNode.next == null ? null : newNode.next.next;
            oldNode = oldNode.next;
            newNode = newNode.next;
        }

        return res;
    }
}

旋转链表

/**
 * 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 rotateRight(ListNode head, int k) {
        //边界条件
        if(head == null || head.next == null){
            return head;
        }

        //计算出链表中节点的个数
        int count = 1;
        ListNode temp = head;
        while(temp.next != null){
            temp = temp.next;
            count++;
        }

        //计算出需要向右移动的个数
        int add = count - k % count;
        //如果移动count个则直接返回头节点
        if(add == count){
            return head;
        }

        //成环
        temp.next = head;
        //移动add次
        while(add-- > 0){
            temp = temp.next;
        }
        ListNode res = temp.next;
        //取消环
        temp.next = null;

        return res;
    }
}