02-链表

• 单链表：值，一个next指针
• 双链表：值，一个last指针，一个next指针

1. 链表反转

• 引用传递

public static void f1(Node node) {
    node = null;
}

@Test
public void test1() {
    Node n1 = new Node(1);
    n1.next = new Node(2);
    // 引用传递。传递的是引用的copy值
    f1(n1);
    System.out.println("n1.value = " + n1.value);
}

public class _01_ReverseList {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }

    /**
     * 单链表反转
     * 在方法中head怎么折腾，上游是不会变的
     */
    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 双链表反转
     */
    public static DoubleNode reverseDoubleList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }

    // -----------------------------------------------------------------------------------

    public static Node testReverseLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        ArrayList<Node> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        int N = list.size();
        for (int i = 1; i < N; i++) {
            list.get(i).next = list.get(i - 1);
        }
        return list.get(N - 1);
    }

    public static DoubleNode testReverseDoubleList(DoubleNode head) {
        if (head == null) {
            return null;
        }
        ArrayList<DoubleNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.get(0).next = null;
        DoubleNode pre = list.get(0);
        int N = list.size();
        for (int i = 1; i < N; i++) {
            DoubleNode cur = list.get(i);
            cur.last = null;
            cur.next = pre;
            pre.last = cur;
            pre = cur;
        }
        return list.get(N - 1);
    }

    // -----------------------------------------------------------------------------------

    // for test
    public static Node generateRandomLinkedList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        size--;
        Node head = new Node((int) (Math.random() * (value + 1)));
        Node pre = head;
        while (size != 0) {
            Node cur = new Node((int) (Math.random() * (value + 1)));
            pre.next = cur;
            pre = cur;
            size--;
        }
        return head;
    }

    // for test
    public static DoubleNode generateRandomDoubleList(int len, int value) {
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        size--;
        DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
        DoubleNode pre = head;
        while (size != 0) {
            DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
            pre.next = cur;
            cur.last = pre;
            pre = cur;
            size--;
        }
        return head;
    }

    // -----------------------------------------------------------------------------------

    // for test
    public static List<Integer> getLinkedListOriginOrder(Node head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.value);
            head = head.next;
        }
        return ans;
    }

    // for test
    public static boolean checkLinkedListReverse(List<Integer> origin, Node head) {
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            head = head.next;
        }
        return true;
    }

    // -----------------------------------------------------------------------------------

    // for test
    public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
        List<Integer> ans = new ArrayList<>();
        while (head != null) {
            ans.add(head.value);
            head = head.next;
        }
        return ans;
    }

    // for test
    public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
        DoubleNode end = null;
        for (int i = origin.size() - 1; i >= 0; i--) {
            if (!origin.get(i).equals(head.value)) {
                return false;
            }
            end = head;
            head = head.next;
        }
        for (int i = 0; i < origin.size(); i++) {
            if (!origin.get(i).equals(end.value)) {
                return false;
            }
            end = end.last;
        }
        return true;
    }

    // -----------------------------------------------------------------------------------

    // for test
    public static void main(String[] args) {
        int len = 50;
        int value = 100;
        int testTime = 100_000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            Node node1 = generateRandomLinkedList(len, value);
            List<Integer> list1 = getLinkedListOriginOrder(node1);
            node1 = reverseLinkedList(node1);
            if (!checkLinkedListReverse(list1, node1)) {
                System.out.println("Oops1!");
            }

            Node node2 = generateRandomLinkedList(len, value);
            List<Integer> list2 = getLinkedListOriginOrder(node2);
            node2 = testReverseLinkedList(node2);
            if (!checkLinkedListReverse(list2, node2)) {
                System.out.println("Oops2!");
            }

            DoubleNode node3 = generateRandomDoubleList(len, value);
            List<Integer> list3 = getDoubleListOriginOrder(node3);
            node3 = reverseDoubleList(node3);
            if (!checkDoubleListReverse(list3, node3)) {
                System.out.println("Oops3!");
            }

            DoubleNode node4 = generateRandomDoubleList(len, value);
            List<Integer> list4 = getDoubleListOriginOrder(node4);
            node4 = reverseDoubleList(node4);
            if (!checkDoubleListReverse(list4, node4)) {
                System.out.println("Oops4!");
            }
        }
        System.out.println("test finish!");
    }

}

2. 单链表Queue

• $O(1)$

public static class Node<V> {
    public V value;
    public Node<V> next;

    public Node(V v) {
        value = v;
        next = null;
    }
}

/**
 * 队列
 */
public static class MyQueue<V> {
    private Node<V> head;
    private Node<V> tail;
    private int size;

    public MyQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    /**
     * offer
     */
    public void offer(V value) {
        Node<V> cur = new Node<V>(value);
        if (tail == null) {
            head = cur;
            tail = cur;
        } else {
            tail.next = cur;
            tail = cur;
        }
        size++;
    }

    /**
     * poll
     * C/C++的同学需要做节点析构的工作
     */
    public V poll() {
        V ans = null;
        if (head != null) {
            ans = head.value;
            head = head.next;
            size--;
        }
        // head > tail
        if (head == null) {
            tail = null;
        }
        return ans;
    }

    // C/C++的同学需要做节点析构的工作
    public V peek() {
        V ans = null;
        if (head != null) {
            ans = head.value;
        }
        return ans;
    }
}

@Test
public void testQueue() {
    MyQueue<Integer> myQueue = new MyQueue<>();
    Queue<Integer> test = new LinkedList<>();
    int testTime = 5_000_000;
    int maxValue = 200_000_000;
    System.out.println("测试开始！");
    for (int i = 0; i < testTime; i++) {
        if (myQueue.isEmpty() != test.isEmpty()) {
            System.out.println("Oops!");
        }
        if (myQueue.size() != test.size()) {
            System.out.println("Oops!");
        }
        double decide = Math.random();
        if (decide < 0.33) {
            int num = (int) (Math.random() * maxValue);
            myQueue.offer(num);
            test.offer(num);
        } else if (decide < 0.66) {
            if (!myQueue.isEmpty()) {
                int num1 = myQueue.poll();
                int num2 = test.poll();
                if (num1 != num2) {
                    System.out.println("Oops!");
                }
            }
        } else {
            if (!myQueue.isEmpty()) {
                int num1 = myQueue.peek();
                int num2 = test.peek();
                if (num1 != num2) {
                    System.out.println("Oops!");
                }
            }
        }
    }
    if (myQueue.size() != test.size()) {
        System.out.println("Oops!");
    }
    while (!myQueue.isEmpty()) {
        int num1 = myQueue.poll();
        int num2 = test.poll();
        if (num1 != num2) {
            System.out.println("Oops!");
        }
    }
    System.out.println("测试结束！");
}

3. 单链表Stack

• $O(1)$

/**
 * 栈
 */
public static class MyStack<V> {
    private Node<V> head;
    private int size;

    public MyStack() {
        head = null;
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void push(V value) {
        Node<V> cur = new Node<>(value);
        if (head == null) {
            head = cur;
        } else {
            cur.next = head;
            head = cur;
        }
        size++;
    }

    public V pop() {
        V ans = null;
        if (head != null) {
            ans = head.value;
            head = head.next;
            size--;
        }
        return ans;
    }

    public V peek() {
        return head != null ? head.value : null;
    }
}

@Test
public void testStack() {
    MyStack<Integer> myStack = new MyStack<>();
    Stack<Integer> test = new Stack<>();
    int testTime = 5_000_000;
    int maxValue = 200_000_000;
    System.out.println("测试开始！");
    for (int i = 0; i < testTime; i++) {
        if (myStack.isEmpty() != test.isEmpty()) {
            System.out.println("Oops!");
        }
        if (myStack.size() != test.size()) {
            System.out.println("Oops!");
        }
        double decide = Math.random();
        if (decide < 0.33) {
            int num = (int) (Math.random() * maxValue);
            myStack.push(num);
            test.push(num);
        } else if (decide < 0.66) {
            if (!myStack.isEmpty()) {
                int num1 = myStack.pop();
                int num2 = test.pop();
                if (num1 != num2) {
                    System.out.println("Oops!");
                }
            }
        } else {
            if (!myStack.isEmpty()) {
                int num1 = myStack.peek();
                int num2 = test.peek();
                if (num1 != num2) {
                    System.out.println("Oops!");
                }
            }
        }
    }
    if (myStack.size() != test.size()) {
        System.out.println("Oops!");
    }
    while (!myStack.isEmpty()) {
        int num1 = myStack.pop();
        int num2 = test.pop();
        if (num1 != num2) {
            System.out.println("Oops!");
        }
    }
    System.out.println("测试结束！");
}

4. 双向链表Deque

/**
 * 双链表实现双端队列
 */
public class _03_DoubleLinkedListToDeque {

    public static class Node<V> {
        public V value;
        public Node<V> last;
        public Node<V> next;

        public Node(V v) {
            value = v;
            last = null;
            next = null;
        }
    }

    public static class MyDeque<V> {
        private Node<V> head;
        private Node<V> tail;
        private int size;

        public MyDeque() {
            head = null;
            tail = null;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        public void pushHead(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                cur.next = head;
                head.last = cur;
                head = cur;
            }
            size++;
        }

        public void pushTail(V value) {
            Node<V> cur = new Node<>(value);
            if (head == null) {
                head = cur;
                tail = cur;
            } else {
                tail.next = cur;
                cur.last = tail;
                tail = cur;
            }
            size++;
        }

        public V pollHead() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last = null;
            }
            return ans;
        }

        public V pollTail() {
            V ans = null;
            if (head == null) {
                return ans;
            }
            size--;
            ans = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next = null;
            }
            return ans;
        }

        public V peekHead() {
            V ans = null;
            if (head != null) {
                ans = head.value;
            }
            return ans;
        }

        public V peekTail() {
            V ans = null;
            if (tail != null) {
                ans = tail.value;
            }
            return ans;
        }

    }

    @Test
    public void testDeque() {
        MyDeque<Integer> myDeque = new MyDeque<>();
        Deque<Integer> test = new LinkedList<>();
        int testTime = 5_000_000;
        int maxValue = 200_000_000;
        System.out.println("测试开始！");
        for (int i = 0; i < testTime; i++) {
            if (myDeque.isEmpty() != test.isEmpty()) {
                System.out.println("Oops!");
            }
            if (myDeque.size() != test.size()) {
                System.out.println("Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                if (Math.random() < 0.5) {
                    myDeque.pushHead(num);
                    test.addFirst(num);
                } else {
                    myDeque.pushTail(num);
                    test.addLast(num);
                }
            } else if (decide < 0.66) {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.pollHead();
                        num2 = test.pollFirst();
                    } else {
                        num1 = myDeque.pollTail();
                        num2 = test.pollLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            } else {
                if (!myDeque.isEmpty()) {
                    int num1 = 0;
                    int num2 = 0;
                    if (Math.random() < 0.5) {
                        num1 = myDeque.peekHead();
                        num2 = test.peekFirst();
                    } else {
                        num1 = myDeque.peekTail();
                        num2 = test.peekLast();
                    }
                    if (num1 != num2) {
                        System.out.println("Oops!");
                    }
                }
            }
        }
        if (myDeque.size() != test.size()) {
            System.out.println("Oops!");
        }
        while (!myDeque.isEmpty()) {
            int num1 = myDeque.pollHead();
            int num2 = test.pollFirst();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束！");
    }

}

5. K个节点组内逆序

• LeetCode
• 给定一个单链表的头节点head，和一个正数k
• 实现k个节点的小组内部逆序，如果最后一组不够k个就不调整
  • 调整前：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
  • k = 3 调整后：3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8

/**
 * K个节点的组内逆序调整
 * https://leetcode.com/problems/reverse-nodes-in-k-group/
 */
public class _04_ReverseNodesInKGroup {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = getKGroupEnd(start, k);
        if (end == null) {
            return head;
        }
        // 第一组的end即为整个链表的head
        head = end;
        reverse(start, end);
        // 第一组的结尾节点
        ListNode lastEnd = start;
        while (lastEnd.next != null) {
            start = lastEnd.next;
            end = getKGroupEnd(start, k);
            if (end == null) {
                return head;
            }
            reverse(start, end);
            // 第n组的end，转化为该组的头，接上组的end
            lastEnd.next = end;
            lastEnd = start;
        }
        return head;
    }

    /**
     * 获取尾index
     */
    public static ListNode getKGroupEnd(ListNode start, int k) {
        while (--k != 0 && start != null) {
            start = start.next;
        }
        return start;
    }

    /**
     * (start, end) 逆序
     */
    public static void reverse(ListNode start, ListNode end) {
        end = end.next;
        ListNode pre = null;
        ListNode cur = start;
        ListNode next;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        start.next = end;
    }

}

6. 两链表相加

• 给定两个链表的头节点head1、head2，认为从左到右是某个数字从低位到高位，返回相加之后的链表
• 4 -> 3 -> 6 -> 1 和 2 -> 5 -> 3 返回 6 -> 8 -> 9 -> 1

/**
 * 两个链表相加
 * https://leetcode.com/problems/add-two-numbers/
 */
public class _05_AddTwoNumbers {

    // 不要提交这个类
    public static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
        int len1 = listLength(head1);
        int len2 = listLength(head2);

        ListNode l = len1 >= len2 ? head1 : head2;
        ListNode s = l == head1 ? head2 : head1;
        ListNode curL = l;
        ListNode curS = s;
        ListNode last = curL;
        int carry = 0;
        int curNum;

        // 1. 短链表处理
        while (curS != null) {
            curNum = curL.val + curS.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
            curS = curS.next;
        }
        // 2. 长链表处理
        while (curL != null) {
            curNum = curL.val + carry;
            curL.val = (curNum % 10);
            carry = curNum / 10;
            last = curL;
            curL = curL.next;
        }

        // 进位处理
        if (carry != 0) {
            last.next = new ListNode(1);
        }
        return l;
    }

    // 求链表长度
    public static int listLength(ListNode head) {
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }
        return len;
    }

}

7. 有序链表合并

• 给定两个有序链表的头节点head1、head2，返回合并之后的大链表，要求依然有序
• 1 -> 3 -> 3 -> 5 -> 7 和 2 -> 2 -> 3 -> 3-> 7 返回 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 3 -> 5 -> 7

/**
 * 两个有序链表的合并
 * https://leetcode.com/problems/merge-two-sorted-lists
 */
public class _06_MergeTwoSortedLinkedList {
    /**
     * 不要提交这个类
     */
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        // 1. 小头，锁死
        ListNode head = (head1.val <= head2.val) ? head1 : head2;

        // 2. 小头下个节点
        ListNode cur1 = head.next;
        // 3. 大头
        ListNode cur2 = (head == head1) ? head2 : head1;

        // 4. 小头
        ListNode pre = head;
        while (cur1 != null && cur2 != null) {
            if (cur1.val <= cur2.val) {
                pre.next = cur1;
                cur1 = cur1.next;
            } else {
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 != null ? cur1 : cur2;
        return head;
    }

}