【CT】LeetCode手撕—21. 合并两个有序链表

题目

• 原题连接：21. 合并两个有序链表

---

1-思路

双指针：题目提供的 list1 和 list2 就是两个双指针

• 通过每次移动 list1 和 list2 并判断二者的值，判断完成后将其 插入到新的当前结点 cur.next 后即可完成链表按升序排列。

---

2- 实现

⭐21. 合并两个有序链表——题解思路

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 定义一个 头结点记录位置ListNode dummyHead = new ListNode(0);ListNode cur = dummyHead;while(list1!=null && list2!=null){if(list1.val<list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}if(list1!=null){cur.next = list1;}if(list2!=null){cur.next = list2;}return dummyHead.next;}
}

---

3- ACM实现

public class twoLinkASC {static class ListNode{int val;ListNode next;ListNode(){}ListNode(int x){val = x;}}public static ListNode mergeTwoLink(ListNode list1,ListNode list2){// 定义虚拟头ListNode dummyHead = new ListNode(-1);ListNode cur = dummyHead;while(list1!=null && list2!=null){if(list1.val<list2.val){cur.next = list1;list1 = list1.next;}else{cur.next = list2;list2 = list2.next;}cur = cur.next;}if(list1!=null){cur.next = list1;}if(list2!=null){cur.next = list2;}return dummyHead.next;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入链表1的长度");ListNode head1=null,tail1=null;int n1 = sc.nextInt();System.out.println("输入链表元素");for(int i = 0 ; i < n1;i++){ListNode nowNode = new ListNode(sc.nextInt());if(head1==null){head1 = nowNode;tail1 = nowNode;}else{tail1.next = nowNode;tail1 = nowNode;}}System.out.println("输入链表2的长度");ListNode head2=null,tail2=null;int n2 = sc.nextInt();System.out.println("输入链表元素");for(int i = 0 ; i < n2;i++){ListNode nowNode = new ListNode(sc.nextInt());if(head2==null){head2 = nowNode;tail2 = nowNode;}else{tail2.next = nowNode;tail2 = nowNode;}}ListNode forRes = mergeTwoLink(head1,head2);while (forRes!=null){System.out.print(forRes.val+" ");forRes = forRes.next;}}
}