秒懂【链表合并】！超清晰图解一步步拆解。

1.思路

假如要合并的两个链表分别为： 1→3→5与 2→4→6，对他们两个链表合并，合并之后的链表为： 1→2→3→4→5→6。结构如下图所示。

alt 第一步：定义临时虚拟头节点与指针变量。指针变量有3个，cur用于操作的链表，h1用于链表1节点值的对比，h2用于链表2节点值的对比。

alt

第二步：循环合并两个链表。

alt

首先比较h1与h2指向节点的值，这时1<2，cur指向值小的链表节点1，h1再后移一个位置，如下图所示：

alt

接下来再更改cur节点的指针域的指向，原来指向3节点，现在让它指向h2对应的节点。更改完之后需要移动cur、h2指针变量。如下图所示：

alt

再来比较h1与h2指向节点的值，此时3<4，需要让cur指向h1对应的节点（值为3的节点）。更改完之后需要移动cur、h1（cur移动到它的下一节点，h1移动到它的下一个节点）。如下图所示：

alt

再来比较h1与h2所指向的节点值，此时：4<5。cur指向较小值的节点4，之后再移动cur、h2到它们的下一个节点，如图所示：

alt

再来比较h1与h2指向节点的值，此时5<6。需要让cur指向5节点，之后再移动cur、h1到它们的下一个节点，如图所示：

alt

此时，h1已经指向Null了，循环结束。

第三步：链接剩余链表节点。

由于h1已经指向Null了，这时只需要将cur指向h2就可以，如下图所示：

alt

此时链表的合并已经完成。

第四步：返回头节点。

链表的头结点为虚拟头结点tmpHead的下一个节点，直接返回即可。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pHead1 ListNode类
# @param pHead2 ListNode类
# @return ListNode类
#
class Solution:
    def Merge(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        # 1.定义临时虚拟头节点与指针变量
        tmp_head = ListNode(-1)
        cur = tmp_head
        p1 = pHead1  # 为了便于理解，定义了h1、h2临时指针变量，其实可以直接用 pHead1、pHead2
        p2 = pHead2

        # 2.循环合并两个链表
        while p1 is not None and p2 is not None:
            # 2.1 cur指针域链接值较小的链表节点，并移动较小值节点的指针变量
            if p1.val <= p2.val:
                cur.next = p1
                p1 = p1.next
            else:
                cur.next = p2
                p2 = p2.next
            cur = cur.next
        # 3. 链接剩余链表节点
        if p1 is not None:
            cur.next = p1
        else:
            cur.next = p2

        # 4. 返回头节点
        return tmp_head.next

2.2 Java代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        // 1.定义临时虚拟头节点与指针变量
        ListNode tmpHead = new ListNode(-1);
        ListNode cur = tmpHead;
        ListNode h1 =
            pHead1; //为了便于理解，定义了h1、h2临时变量，其实可以直接用 pHead1、pHead2
        ListNode h2 = pHead2;

        // 2.循环合并两个链表
        while (h1 != null && h2 != null) {
            // 2.1 cur指针域链接值较小的链表节点，并移动较小值节点的指针变量
            if (h1.val <= h2.val) {
                cur.next = h1;
                h1 = h1.next;
            } else {
                cur.next = h2;
                h2 = h2.next;
            }
            // 2.2 移动cur指针变量
            cur = cur.next;
        }
        // 3.链接剩余链表节点
        if (h1 != null) {
            cur.next = h1;
        } else {
            cur.next = h2;
        }
        // 4.返回头节点
        return tmpHead.next;
    }


}

2.3 Go代码

package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
func Merge(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	// write code here
	// 1.定义临时虚拟头节点与指针变量
	tmpHead := &ListNode{Val: -1}
	cur := tmpHead
	h1 := pHead1 //为了便于理解，定义了h1、h2临时指针变量，其实可以直接用 pHead1、pHead2
	h2 := pHead2

	// 2.循环合并两个链表
	for h1 != nil && h2 != nil {
		// 2.1 cur指针域链接值较小的链表节点，并移动较小值节点的指针变量
		if h1.Val <= h2.Val {
			cur.Next = h1
			h1 = h1.Next
		} else {
			cur.Next = h2
			h2 = h2.Next
		}
		// 2.2 移动cur指针变量
		cur = cur.Next
	}
	// 3.链接剩余链表节点
	if h1 != nil {
		cur.Next = h1
	} else {
		cur.Next = h2
	}
	// 4.返回头节点
	return tmpHead.Next
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构