合并两个有序链表

灰太狼 2023-03-01 12:52 8阅读 0赞

# 合并两个有序链表 #

## 1、题目 ##

*  题目要求：将两个升序链表合并为一个新的**升序**链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *  **示例：**

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

## 2、代码思路 ##

1.  `preNode` 为待排序节点的前驱结点， `node1` 和 `node2` 分别指向两个链表中待排序的节点，谁小谁就排在 `preNode` 后面
    
    ![image-20200726105943433][]
2.  进行比较：由于 `node1` 指向的节点的值较小，让 `preNode` 指向 `node1` 指向的节点
    
    ![image-20200726110213463][]
3.  然后 `preNode` 指针后移 ，`node1` 指针后移
    
    ![image-20200726110331016][]
4.  再次进行比较：由于 `node2` 指向的节点的值较小，让 `preNode` 指向 `node2` 指向的节点
    
    ![image-20200726110523216][]
5.  直至 `node1 == null` 或者 `node2 == null`
    
    ![image-20200726110805970][]
6.  最后链表 `2` 还有剩余元素，将 `preNode` 指向 `node2` 指向的节点，将剩余元素接在新链表的最后![image-20200726110901417][]

## 3、代码实现 ##

### 3.1、链表节点定义 ###

//节点
    class Node {
        
    	public Integer data;
    	public Node next;
    
    	public Node(Integer data) {
        
    		this.data = data;
    	}
    
    	public String toString() {
        
    		return data.toString();
    	}
    }

### 3.2、链表的定义 ###

//链表类
    class SingleLinkedList {
        
    
    	public Node head = new Node(0);
    
    	public void add(Node node) {
        
    		// 首节点指针不能移动哦，需要定义辅助指针
    		Node preNode = head;
    		while (preNode.next != null) {
        
    			preNode = preNode.next;
    		}
    		preNode.next = node;
    	}
    
    	public void show() {
        
    		// 首节点指针不能移动哦，需要定义辅助指针
    		Node curNode = head.next;
    		while (curNode != null) {
        
    			System.out.print(curNode.data + "-->");
    			curNode = curNode.next;
    		}
    		System.out.println();
    	}
    }

### 3.3、链表合并 ###

public static SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) {
        
        // 新链表的头结点
        Node head = new Node(0);
        // preNode 指向当前待排序节点的前一个节点
        Node preNode = head;
    
        // 设置新链表的头结点
        SingleLinkedList mergeList = new SingleLinkedList();
        mergeList.head = head;
    
        // node1 初始值默认指向 list1 的首节点
        Node node1 = list1.head.next;
        // node2 初始值默认指向 list2 的首节点
        Node node2 = list2.head.next;
    
        // 当 node1 和 node2 其中一个为 null 时，就代表有一个链表已经到头啦
        while (node1 != null && node2 != null) {
        
            // 将值小的节点排在前面（升序排列），并且后移 node1 或 node2 指针
            if (node1.data < node2.data) {
        
                preNode.next = node1;
                node1 = node1.next;
            } else {
        
                preNode.next = node2;
                node2 = node2.next;
            }
            // preNode 后移，为下一次排序做准备
            preNode = preNode.next;
        }
    
        // 最后链上还有剩余节点的链表
        preNode.next = (node1 == null) ? node2 : node1;
    
        // 返回合并后的链表
        return mergeList;
    }

### 3.4、测试代码 ###

*  代码

public static void main(String[] args) {
        
    
        SingleLinkedList list1 = new SingleLinkedList();
        list1.add(new Node(1));
        list1.add(new Node(3));
        list1.add(new Node(5));
        list1.add(new Node(7));
        list1.add(new Node(9));
    
        SingleLinkedList list2 = new SingleLinkedList();
        list2.add(new Node(2));
        list2.add(new Node(4));
        list2.add(new Node(6));
        list2.add(new Node(6));
        list2.add(new Node(8));
        list2.add(new Node(10));
        list2.add(new Node(11));
        list2.add(new Node(12));
    
        // 合并链表
        SingleLinkedList mergeList = merge(list1, list2);
        System.out.println("合并后的链表如下~~~");
        mergeList.show();
    }

*  程序运行结果

合并后的链表如下~~~
    1-->2-->3-->4-->5-->6-->6-->7-->8-->9-->10-->11-->12-->

### 3.5、全部代码 ###

public class MergeList {
        
    	public static void main(String[] args) {
        
    
    		SingleLinkedList list1 = new SingleLinkedList();
    		list1.add(new Node(1));
    		list1.add(new Node(3));
    		list1.add(new Node(5));
    		list1.add(new Node(7));
    		list1.add(new Node(9));
    
    		SingleLinkedList list2 = new SingleLinkedList();
    		list2.add(new Node(2));
    		list2.add(new Node(4));
    		list2.add(new Node(6));
    		list2.add(new Node(6));
    		list2.add(new Node(8));
    		list2.add(new Node(10));
    		list2.add(new Node(11));
    		list2.add(new Node(12));
    
    		// 合并链表
    		SingleLinkedList mergeList = merge(list1, list2);
    		System.out.println("合并后的链表如下~~~");
    		mergeList.show();
    	}
    
    	public static SingleLinkedList merge(SingleLinkedList list1, SingleLinkedList list2) {
        
    		// 新链表的头结点
    		Node head = new Node(0);
    		// preNode 指向当前待排序节点的前一个节点
    		Node preNode = head;
    
    		// 设置新链表的头结点
    		SingleLinkedList mergeList = new SingleLinkedList();
    		mergeList.head = head;
    
    		// node1 初始值默认指向 list1 的首节点
    		Node node1 = list1.head.next;
    		// node2 初始值默认指向 list2 的首节点
    		Node node2 = list2.head.next;
    
    		// 当 node1 和 node2 其中一个为 null 时，就代表有一个链表已经到头啦
    		while (node1 != null && node2 != null) {
        
    			// 将值小的节点排在前面（升序排列），并且后移 node1 或 node2 指针
    			if (node1.data < node2.data) {
        
    				preNode.next = node1;
    				node1 = node1.next;
    			} else {
        
    				preNode.next = node2;
    				node2 = node2.next;
    			}
    			// preNode 后移，为下一次排序做准备
    			preNode = preNode.next;
    		}
    
    		// 最后链上还有剩余节点的链表
    		preNode.next = (node1 == null) ? node2 : node1;
    
    		// 返回合并后的链表
    		return mergeList;
    	}
    }
    
    //链表类
    class SingleLinkedList {
        
    
    	public Node head = new Node(0);
    
    	public void add(Node node) {
        
    		// 首节点指针不能移动哦，需要定义辅助指针
    		Node preNode = head;
    		while (preNode.next != null) {
        
    			preNode = preNode.next;
    		}
    		preNode.next = node;
    	}
    
    	public void show() {
        
    		// 首节点指针不能移动哦，需要定义辅助指针
    		Node curNode = head.next;
    		while (curNode != null) {
        
    			System.out.print(curNode.data + "-->");
    			curNode = curNode.next;
    		}
    		System.out.println();
    	}
    }
    
    //节点
    class Node {
        
    	public Integer data;
    	public Node next;
    
    	public Node(Integer data) {
        
    		this.data = data;
    	}
    
    	public String toString() {
        
    		return data.toString();
    	}
    }

[image-20200726105943433]: /images/20230208/50d5648cad4743628f645facc042f60c.png
[image-20200726110213463]: /images/20230208/602701d79fcb4df48454db3fa5149439.png
[image-20200726110331016]: /images/20230208/bac652ab1e76470684d91a042b93ba2a.png
[image-20200726110523216]: /images/20230208/50fc751c2e2b44829590a6e52aa8adb9.png
[image-20200726110805970]: /images/20230208/066b7e9e0e9f4494b31d3cd2767c3e22.png
[image-20200726110901417]: /images/20230208/e7d35795d86748d18cf4400cf2c2b976.png