算法题之合并两个有序单向链表

算法题之合并两个有序单向链表

题目描述

题目分析

代码实现

思路1代码:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //首先判断两个头结点是否都为null,如果均为null则直接返回null即可 if (l1 == null && l2 == null) { return null; } //定义一个新的链表头节点:仅仅表示一个头节点标志位 ListNode head = new ListNode(); //首先将两个链表的所有节点压入栈 Stack<ListNode> stack = new Stack<>(); ListNode head1 = l1; ListNode head2 = l2; while (head1 != null) { stack.push(head1); head1 = head1.next; } while (head2 != null) { stack.push(head2); head2 = head2.next; } //添加节点[根据val值从小到大的顺序] while (stack.size() > 0) { addNode(head,stack.pop()); } //添加节点完毕,直接返回head的next域即为合并之后的新的头节点 return head.next; } private void addNode(ListNode head, ListNode pop) { ListNode temp = head; while (true) { if (temp.next == null) {//表示当前链表为空或者遍历到链表的最后一个元素,直接返回 break; } if (temp.next.val >= pop.val) {//找到pop节点的添加位置 break; } temp = temp.next; } //while循环结束,即找到pop添加的位置:即temp的下一个节点即为pop的位置 //所以将pop的下一个节点指向temp的next域,再将temp的下一个节点指向pop pop.next = temp.next; temp.next = pop; }

思路2代码:

public ListNode mergeTwoLists(ListNode l1,ListNode l2) { if (l1 == null) { return l2; }else if (l2 == null) { return l1; }else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next,l2); return l1; }else { //即l1.val >= l2.val l2.next = mergeTwoLists(l1,l2.next); return l2; } }