算法题--合并有序链表

> 字节跳动一面

合并有序链表

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

来源：[力扣](https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/)

```
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
```

这题比较简单，依次比较拼接到新链表上即可。注意一点是不需要new许多新的节点了，直接改变原链表节点的next指向即可。

另外我这边写链表习惯有head头结点，头结点是不放内容的，但是LeeCode的头结点就是第一个节点，是放内容的，所以直接将我的代码粘贴到力扣可能不太行。（这个代码是后来写的，力扣上的这道题很久前就刷过了）

代码：

```java
package com.example.demo.core.Leecode;

/**
 * @author: HanXu
 * on 2022/2/25
 * Class description: 合并有序链表
 */
public class MergeOrderLinked {
    //链表节点
    static class Node {
        int val;
        Node next;

public Node() {
        }

public Node(int val) {
            this.val = val;
        }
    }

public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 8, 9};
        int[] arr2 = {-1, 2, 7, 10, 11};
        //合并后{-1, 1, 2, 3, 5, 7, 8, 9, 10, 11}
        Node node1 = buildLinked(arr1);
        Node node2 = buildLinked(arr2);
        printLinked(node1);
        printLinked(node2);

Node node = mergeLinked(node1, node2);
        printLinked(node);
        /*
        1 3 5 8 9
        -1 2 7 10 11
        -1 1 2 3 5 7 8 9 10 11
         */
    }

/**
     * 合并有序链表：两个链表元素都是从小到大，合并两个有序链表，要求合并后链表依旧有序。
     * 不用创建新的链表空间，改变next指向即可
     * @param node1
     * @param node2
     * @return
     */
    public static Node mergeLinked(Node node1, Node node2) {
        //新链表头指针
        Node head = new Node();
        //pNode指针是一个“拼接工”，将有序的元素拼接起来
        Node pNode = head;
        //两个链表移动到第一个元素
        node1 = node1.next;
        node2 = node2.next;
        //比较，选择
        while (node1 != null && node2 != null) {
            if (node1.val < node2.val) {
                pNode.next = node1;
                node1 = node1.next;
            } else {
                pNode.next = node2;
                node2 = node2.next;
            }
            pNode = pNode.next;
        }
        //最多只有一个链表不为空，不为空的部分依次接上去即可。
        while (node1 != null) {
            pNode.next = node1;
            node1 = node1.next;
            pNode = pNode.next;
        }
        while (node2 != null) {
            pNode.next = node2;
            node2 = node2.next;
            pNode = pNode.next;
        }
        return head;
    }

/**
     * 打印链表
     * @param node
     */
    public static void printLinked(Node node) {
        while (node.next != null) {
            node = node.next;
            System.out.print(node.val + " ");
        }
        System.out.println();
    }

/**
     * 构建链表
     * @param arr
     * @return 返回头节点
     */
    public static Node buildLinked(int[] arr) {
        Node head = new Node();
        Node pNode = head;
        for (int i = 0; i < arr.length; i++) {
            Node node = new Node(arr[i]);
            pNode.next = node;
            pNode = node;
        }
        return head;
    }
}
```

另一道相似的题目：[双指针之有序数组的平方](http://riun.xyz/work/195)

算法题--合并有序链表

文章目录

发表评论