［LeetCode］Merge Two Sorted Lists-白红宇

［LeetCode］Merge Two Sorted Lists

阅读量：2237 次

发布时间：2019-05-09

本文共 1952 字，大约阅读时间需要 6 分钟。

解题思路：

1，添加一个 dummy node作为header，这样不用纠结 header是谁了

2，如果两个list长度不同，怎么处理简洁？请参考下述代码

对java的认识：

1，对象都是引用类型的，对链表的操作用 . 而C＋＋中用 ->

public class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode dummy = new ListNode(0);        ListNode p = dummy;        while(l1 != null || l2 != null){            int x = (l1 != null ? l1.val : Integer.MAX_VALUE);            int y = (l2 != null ? l2.val : Integer.MAX_VALUE);            if (x > y){                p.next = l2;                l2 = l2.next;            }else{                p.next = l1;                l1 = l1.next;            }            p = p.next;        }        return dummy.next;    }}

————————第一遍的解题方法总是很不简洁－－－－－－－－－－－－

解题思路：

边界条件：至少某一个list为NULL；

前条件：选好head，cur = head, cur1 = l1; cur2 = l2;

不变式：只要l1 和 l2都不为NULL，看那个val小，就加在cur后面, 再cur = cur->next

结束条件：有一个list为空，把另外一个list整体加在cur后面

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {        if (l1 == NULL){            return l2;        }else if (l2 == NULL){            return l1;        }         ListNode* head = NULL;         ListNode* cur1 = l1;         ListNode* cur2 = l2;         if ( cur1->val > cur2->val ){             head = cur2;             cur2 = cur2->next;         }else{             head = cur1;             cur1 = cur1->next;         }         ListNode* cur = head;         while(cur1 != NULL && cur2 != NULL){             if (cur1->val > cur2->val){                 cur->next = cur2;                 cur2 = cur2->next;             }else{                 cur->next = cur1;                 cur1 = cur1->next;             }             cur = cur->next;         }         if (cur1 != NULL){             cur->next = cur1;         }else if (cur2 != NULL){             cur->next = cur2;         }        return head;    }};

转载地址：http://mjpbb.baihongyu.com/

你可能感兴趣的文章

Struts2中的session、request、respsonse获取方法

SpringMVC中时间格式转换的解决方案

查看>>

post和get请求相关知识点

查看>>