合并两个有序的单链表，合并之后的新链表依然有序

忘是亡心i 2023-06-30 09:06 11阅读 0赞

package com.zzb.datastructure.singlelist;
    
    import java.io.Serializable;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/1/15 16:55
     * @Description:
     * 合并两个有序的单链表，合并之后的新链表依然有序
     */
    public class MergeOrderSingleLinkedListTest {
        public static void main(String[] args) {
            Node node1 = new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
    
            Node node4 = new Node(4);
            Node node5 = new Node(5);
            Node node6 = new Node(6);
    
            node1.setNext(node2);
            node2.setNext(node3);
    
            node4.setNext(node5);
            node5.setNext(node6);
    
            Node result = merge(node1,node4);
    
            while(result != null) {
                System.out.print(result.getData() + "\t");
                result = result.getNext();
            }
            /*
            1	2	3	4	5	6*/
        }
    
        private static Node merge(Node node1, Node node2) {
            // 判断需要合并的链表是否为空
            if(node1 == null && node2 == null) {
                throw new RuntimeException("需要合并的两条链表都为空！");
            }
            // 一条链表为空，直接返回另一条链表
            if(node1 == null) {
                return node2;
            }
            if(node2 == null) {
                return node1;
            }
            // 合并后的新链表的头结点
            Node head = null;
            // 选出最小值作为合并后的新链表的头结点
            if(node1.getData() <= node2.getData()) {
                head = node1;
                // 后移节点
                node1 = node1.getNext();
            } else {
                head = node2;
                // 后移节点
                node2 = node2.getNext();
            }
            // 临时变量，用来链接合并链表的节点
            Node temp = head;
            // 循环条件
            while(node1 != null && node2 != null) {
                if(node2.getData() <= node2.getData()) {
                    temp.setNext(node1);
                    // 后移节点
                    node1 = node1.getNext();
                } else {
                    temp.setNext(node2);
                    // 后移节点
                    node2 = node2.getNext();
                }
                // 临时变量，用来链接合并链表的节点
                temp = temp.getNext();
            }
            if(node1 == null) {
                temp.setNext(node2);
            }
            if(node2 == null) {
                temp.setNext(node1);
            }
            return head;
        }
    }
    
    class Node implements Serializable {
        private static final long serialVersionUID = 6539573865089177060L;
    
        private int data;
        private Node next;
    
        public Node(int data) {
            this.data = data;
        }
    
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    ", next=" + next +
                    '}';
        }
    }