LeetCode -- Merge Two sorted lists
题目描述:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
就是把两个已经排序的链表进行合并。
思路:
将链表l2合并到l1中,逐个遍历l2
如果l1不是最后一个:
l1<=l2 && l2 <= l1.next :移除l2,将l2放在l1.next
l2 < l1 : 将l2.next=l1 并替换头结点
else: l1=l1.next
如果l1是最后结点:
l2 > l1:l1.next = l2
else : 将l2.next = l1并替换头结点
实现代码:
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
就是把两个已经排序的链表进行合并。
思路:
将链表l2合并到l1中,逐个遍历l2
如果l1不是最后一个:
l1<=l2 && l2 <= l1.next :移除l2,将l2放在l1.next
l2 < l1 : 将l2.next=l1 并替换头结点
else: l1=l1.next
如果l1是最后结点:
l2 > l1:l1.next = l2
else : 将l2.next = l1并替换头结点
实现代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
// merge l2 into l1
ListNode head = l1;
while(l2 != null){
if(l1.next != null){
if(l2.val >= l1.val && l2.val <= l1.next.val){
var t = Remove(ref l2);
t.next = l1.next;
l1.next = t;
}
else if(l2.val < l1.val){
var t = Remove(ref l2);
t.next = l1;
head = t;
l1 = t;
}
else{
l1 = l1.next;
}
}
else{
if(l1.val < l2.val){
l1.next = Remove(ref l2);
}
else{
var t = Remove(ref l2);
t.next = l1;
head = t;
l1 = t;
}
}
}
return head;
}
private ListNode Remove(ref ListNode n)
{
ListNode t = new ListNode(n.val);
if(n.next == null){
n = null;
}
else{
n.val = n.next.val;
n.next = n.next.next;
}
return t;
}
}