大厂必考链表算法-反转链表/合并有序K链表

Node节点

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

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

        public void print() {
            Node head = this;
            StringBuffer sb = new StringBuffer();
            while (head != null) {
                sb.append(head == this ? head.value : "-->" + head.value);
                head = head.next;
            }
            System.out.println(sb.toString());
        }
    }

思路：

1. 建立两个指针pre next 以及已知的head节点
2. next指针存储需要反转节点的下一个节点信息 pre指针存储需要反转的节点的上一个节点信息
3. 反转当前节点 将head.next --> pre
4. 将pre向后移动 head节点向后移动 继续反转后一个节点
5. 重复3 4 步骤 直到head == null 表示已经反转完毕

public static Node reserve2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node pre = null;
        Node next = null;
        //只看next = head.next ; head = next 就是在将head向后移动
        //中间进行了head节点的反转操作 head.next = pre
        //最后将pre的位置向后移动
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return head;
    }

思路：

1. 每个节点都需要设置 node.next.next = node, node.next = null
2. 递归到最后的5节点时，开始反转链表 4.next.next = 4; 4.next = null
3. 递归方法返回5节点 此时链表为 1 --> 2 --> 3 --> 4 <-- 5
4. 递归层层返回 则完成了链表反转

public static Node reserve(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node cur = reserve(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }

为什么返回的cur节点就是反转后的头结点?
cur节点在最后return head的时候返回了最后的5节点，在后续返回的时候一直都没有修改，修改的是进入递归的head节点指向,
其他递归返回的都是最开始的5节点

思路：

1. 建立两个指针pre next 以及已知的head节点
2. next指针存储需要反转节点的下一个节点信息 pre指针存储需要反转的节点的上一个节点信息
3. 反转当前节点 将head.next --> pre ; head.last --> next
4. 将pre向后移动 head节点向后移动 继续反转后一个节点
5. 重复2 3 步骤 直到head == null 表示已经反转完毕

public static DoubleNode reserveDoubleNode(DoubleNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        DoubleNode pre = null;
        DoubleNode next = null;
        //只看next = head.next ; head = next 就是在将head向后移动
        //中间进行了head节点的反转操作
        //最后将pre的位置向后移动
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }

既然这个链表是双向的了，直接把头结点当成尾节点，尾节点当成头结点不就直接反转了吗？

从逻辑上看，这样确实就算是反转了.但是对于节点的last和next指向是不一样的 。
之前的是4.last = 3 ；4.next = 5
反转后是4.last = 5 ; 4.next = 3

测试链表反转

    public static Node genListNode(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;
    }

    
    public static DoubleNode genDoubleListNode(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;
    }

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

    
    public static boolean checkNodeReserve(List 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;
    }

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

    
    public static boolean checkDoubleNodeReverse(List 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;
    }

	@Test
    public void testReserve() {
        int len = 5;
        int value = 100;
        int testTime = 100000;
        System.out.println("test begin!");
        for (int i = 0; i < testTime; i++) {
            Node node1 = genListNode(len, value);

            List list1 = node2List(node1);

            node1.print();
            node1 = reserve(node1);
            node1.print();
            if (!checkNodeReserve(list1, node1)) {
                System.out.println("Oops1!");
            }

            DoubleNode node3 = genDoubleListNode(len, value);
            List list3 = doubleNode2List(node3);

            node3 = reserveDoubleNode(node3);
            if (!checkDoubleNodeReverse(list3, node3)) {
                System.out.println("Oops3!");
            }

        }
        System.out.println("test finish!");

    }

public static class NodeToQueue {

        //队列大小
        private int size;
        private Node head;
        //没有尾节点时添加元素时间复杂度变为O(n)
        private Node tail;

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

        public int size(){
            return size;
        }

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

        public void offer(int value) {
            Node node = new Node<>(value);
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = node;
            }
            size++;
        }

        public int poll() {
            int value = -1;
            if (head != null) {
                value = head.value;
                head = head.next;
                size--;
            }
            //help gc
            if (head == null) {
                tail = null;
            }
            return value;
        }

        public int peek() {
            if (head != null) {
                return head.value;
            }
            return -1;
        }
    }

测试：

@Test
    public void testQueue() {
        NodeToQueue myQueue = new NodeToQueue();
        Queue test = new LinkedList<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        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("测试结束！");
    }

public static class NodeToStack {
        private Node head;
        private int size;

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

        public int size(){
            return size;
        }

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

        public int peek(){
            int value = -1;
            if (head != null) {
                value = head.value;
            }
            return value;
        }

        public void push(int value) {
            Node node = new Node(value);
            if (head == null) {
                head = node;
            } else {
                //新加入的节点当做头节点 满足后入先出
                node.next = head;
                head = node;
            }
            size++;
        }

        public int pop() {
            int value = -1;
            if (head != null) {
                //弹出头结点元素
                value = head.value;
                head = head.next;
                size--;
            }
            return value;
        }
    }

测试：

 @Test
    public  void testStack() {
        NodeToStack myStack = new NodeToStack();
        Stack test = new Stack<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        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("测试结束！");
    }

public class LinkedDeque {
    private DoubleListNode head;
    private DoubleListNode tail;
    private int size;

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

    public void addHead(T data) {
        DoubleListNode cur = new DoubleListNode(data);
        if (head == null) {
            head = cur;
            tail = cur;
        } else {
            cur.next = head;
            head.last = cur;
            head = cur;
        }
        size++;
    }

    public void addTail(T data) {
        DoubleListNode cur = new DoubleListNode(data);
        if (head == null) {
            head = cur;
            tail = cur;
        } else {
            cur.last = tail;
            tail.next = cur;
            tail = cur;
        }
        size++;
    }

    public T pollHead() {
        if (head == null) {
            return null;
        }
        DoubleListNode cur = head;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            head = head.next;
            head.last = null;
            cur.next = null;
        }
        size--;
        return cur.data;
    }

    public T pollTail() {
        if (head == null) {
            return null;
        }
        DoubleListNode cur = tail;
        if (head == tail) {
            head = null;
            tail = null;
        } else {
            tail = tail.last;
            tail.next = null;
            cur.last = null;
        }
        size--;
        return cur.data;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty() {
        return head == null;
    }

    public T peekHead(){
        T ans = null;
        if (head != null) {
            ans = head.data;
        }
        return ans;
    }

    public T peekTail(){
        T ans = null;
        if (tail != null) {
            ans = tail.data;
        }
        return ans;
    }
}

测试：

@Test
    public  void testDeque() {
        LinkedDeque myDeque = new LinkedDeque<>();
        Deque test = new LinkedList<>();
        int testTime = 5000000;
        int maxValue = 200000000;
        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.addHead(num);
                    test.addFirst(num);
                } else {
                    myDeque.addTail(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("测试结束！");
    }

双端队列实现队列 : 头节点插入 尾节点弹出 或者 头节点弹出 尾节点插入即可

public class MyQueue {
    private LinkedDeque queue;

    public MyQueue() {
        queue = new LinkedDeque<>();
    }

    public void push(T data) {
        queue.addHead(data);
    }

    public T poll() {
        return queue.pollTail();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

头节点插入、头节点弹出 或者 尾节点插入、尾节点弹出

public class MyStack {
    private LinkedDeque queue;

    public MyStack() {
        queue = new LinkedDeque<>();
    }

    public void push(T data) {
        queue.addHead(data);
    }

    public T pop() {
        return queue.pollHead();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

}

问题描述：

力扣地址：https://leetcode.cn/problems/reverse-nodes-in-k-group/
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

思路：

1. 先构造reverse(ListNode start, ListNode end)方法 反转指定范围内的链表
2. 再构造getKGroupEnd(ListNode start, int k)方法 根据k的到这组链表的尾节点
3. 将链表按照getKGroupEnd 分割，每组链表单独反转，
4. 反转后将第一组的尾节点关联到第二组的头节点中

    public static Node reserveKGroup(Node head, int k){
        Node start = head;
        Node end = getKGroupEnd(head, k);
        //长度不满足K 直接返回
        if(end == null) {
            return head;
        }
        //固定新链表的头结点，这个节点不会变动
        head = end;
        //反转第一组的链表
        reserve(start, end);
        //反转完成后 start节点就是下一组的头结点的上一个节点
        Node lastEnd = start;
        //下一组的头结点不为空
        while (lastEnd.next != null) {
            start = lastEnd.next;
            end = getKGroupEnd(start, k);
            //下一组链表长度不足K 直接返回
            if(end == null) {
                return head;
            }
            //反转下一组的链表
            reserve(start, end);
            //设置上一组的尾节点下一个元素是这组的头节点
            lastEnd.next = end;
            //移动lastEnd到下一组的链表的位置
            lastEnd = start;
        }
        return head;
    }

    
    private static void reserve(Node start, Node end) {
        end = end.next;
        Node pre = null;
        //定义临时节点存储头节点位置
        Node cur = start;
        Node next = null;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //将头结点的下一个节点指向到end 防止链表断开
        start.next = end;
    }

    
    private static Node getKGroupEnd(Node start, int k) {
        while (--k !=0 && start != null) {
            start = start.next;
        }
        return start;
    }

力扣地址：https://leetcode.cn/problems/add-two-numbers/
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路：

1.先找到较长的链表 通过短链表循环遍历
2.使用变量up存储进位信息 带入到下一个链表元素相加
3.使用相加结果的值/10 = 覆盖到长链表对应元素中
4.最后判断长链表是否遍历完 以及是否存在进位信息

public static Node addTwoNode(Node head1, Node head2){
        int len1 = getNodeLen(head1);
        int len2 = getNodeLen(head2);
        Node curL = len1 >= len2 ? head1 : head2;
        Node curS = curL == head1 ? head2 : head1;
        //记录新的链表头结点
        Node result = curL;
        //记录长链表的最后一个节点位置
        Node last = curL;
        //链表值相加结果
        int curNum = 0;
        //是否存在进位信息
        int up = 0;
        //短链表和长链表相加
        while (curS != null) {
            curNum = curL.value + curS.value + up;
            up = curNum /10;
            int newNum = curNum % 10;
            curL.value = newNum;
            curS = curS.next;
            last = curL;
            curL = curL.next;
        }
        //长链表还有元素
        while(curL != null) {
            curNum = curL.value + up;
            curL.value = (curNum % 10);
            up = curNum / 10;
            last = curL;
            curL = curL.next;
        }
        if(up != 0) {
            Node end = new Node(up);
            //需要一个节点记录curL最后节点的信息 否则这里得到的可能是null
            last.next = end;
        }
        return result;
    }

    private static int getNodeLen(Node head) {
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }

力扣地址：https://leetcode.cn/problems/merge-two-sorted-lists/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    public Node mergeTwoNode(Node head1, Node head2){
        if(head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        Node head = new Node(-1);
        Node pre = head;
        while (head1 != null && head2 != null) {
            if(head1.value <= head2.value) {
                pre.next = head1;
                head1 = head1.next;
            } else {
                pre.next = head2;
                head2 = head2.next;
            }
            //pre指向新添加的节点位置
            pre = pre.next;
        }
        //合并最后不为空的链表
        pre.next = head1 == null ? head2 : head1;
        return head.next;
    }

测试：

private Node sortNode(Node node) {
        List list = node2List(node);
        Collections.sort(list);
        Node head = new Node(-1);
        Node r = head;
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            head.next = new Node(iterator.next());
            head = head.next;
        }
        return r.next;
    }

    @Test
    public void testMergeTwoNode(){
        for (int i = 0; i < 50; i++) {
            Node head1 = genListNode(10, 9);
            Node head2 = genListNode(6, 9);
            if (Objects.nonNull(head1)) {
                head1 = sortNode(head1);
                head1.print();
            }
            if (Objects.nonNull(head2)) {
                head2 = sortNode(head2);
                head2.print();
            }
            if(head1 == null && head2 == null) {
                continue;
            }
            Node node1 = mergeTwoNode(head1, head2);
            System.out.println("合并结果：");
            node1.print();
            System.out.println();
        }
    }

思路：

1. 构造大小为K的优先级队列，默认是小根堆。将K个链表第一个元素放入到队列中
2. 队列弹出第一个元素就是合并的队列的头节点
3. 弹出队列的元素的下一个元素进入队列比较大小并弹出新的最小元素
4. 依次压入和弹出元素即可

public static Node mergeKNode(Node[] list) {
        if(list == null) {
            return null;
        }
        //构造小根堆
        PriorityQueue> queue = new PriorityQueue(list.length,
                (Comparator>) (o1, o2) -> o1.value - o2.value);
        //将每个链表第一个元素放入队列中
        for (int i = 0; i < list.length; i++) {
            if(list[i] != null) {
                queue.offer(list[i]);
            }
        }
        //设置合并的链表的头节点
        Node head = queue.poll();
        //临时节点 向后添加元素
        Node pre = head;
        //记录需要添加到队列中的链表元素
        Node cur = head;
        while(!queue.isEmpty()) {
            //判空
            if(cur.next != null) {
                queue.offer(cur.next);
            }
            cur = queue.poll();
            pre.next = cur;
            pre = pre.next;
        }
        return head;
    }