本文共 4738 字，大约阅读时间需要 15 分钟。

合并两个有序链表

1、题目

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

• 示例：

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

2、代码思路

1. preNode 为待排序节点的前驱结点， node1 和 node2 分别指向两个链表中待排序的节点，谁小谁就排在 preNode 后面

   

2. 进行比较：由于 node1 指向的节点的值较小，让 preNode 指向 node1 指向的节点

   

3. 然后 preNode 指针后移 ，node1 指针后移

   

4. 再次进行比较：由于 node2 指向的节点的值较小，让 preNode 指向 node2 指向的节点

   

5. 直至 node1 == null 或者 node2 == null

   

6. 最后链表 2 还有剩余元素，将 preNode 指向 node2 指向的节点，将剩余元素接在新链表的最后

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();	}}

转载地址：http://iifc.baihongyu.com/