Java面试题：链表-合并两个排序的链表

描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例

输入：
{1,3,5}, {2,4,6}返回值：
{1,2,3,4,5,6}

原题地址：https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

代码实现

package com.example.demo.linked;public class ListNode {int val;ListNode next = null;public ListNode(int val) {this.val = val;}
}

package com.example.demo.linked;public class LinkUtil {public static void printNodeList(ListNode head) {ListNode current = head;while (current != null) {System.out.print(current.val + " ");current = current.next;}System.out.println();}
}

package com.example.demo.linked;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param pHead1 ListNode类* @param pHead2 ListNode类* @return ListNode类*/public ListNode Merge(ListNode pHead1, ListNode pHead2) {// write code hereif (pHead1 == null) {return pHead2;} else if (pHead2 == null) {return pHead1;}ListNode head = new ListNode(0);ListNode current = head;while (true) {if (pHead1 == null) {current.next = pHead2;break;} else if (pHead2 == null) {current.next = pHead1;break;} else {if (pHead1.val <= pHead2.val) {current.next = pHead1;pHead1 = pHead1.next;} else {current.next = pHead2;pHead2 = pHead2.next;}current = current.next;}}return head.next;}public static void main(String[] args) {// 1 3 5ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(3);ListNode listNode3 = new ListNode(5);listNode1.next = listNode2;listNode2.next = listNode3;LinkUtil.printNodeList(listNode1);// 2 4 6ListNode listNodeA = new ListNode(2);ListNode listNodeB = new ListNode(4);ListNode listNodeC = new ListNode(6);listNodeA.next = listNodeB;listNodeB.next = listNodeC;LinkUtil.printNodeList(listNodeA);// 合并链表ListNode listNode = new Solution().Merge(listNode1, listNodeA);LinkUtil.printNodeList(listNode);}
}