题目描述: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.
首先拿到这道题目的时候,我觉得挺简单的,严蔚敏那本数据结构里面有这样的一个例题,我觉得不会很难,然后很快就写完了,但是这个题目中的链表和书中的链表稍有差别,书中有头指针,但是这里却没有头指针,有头指针的链表结构和没有头指针的链表差别在,有头指针的链表在插入删除时,所有的操作是一样的,相反,没有头指针的,第一个节点操作跟后面的节点是不一样的。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // Note: The Solution object is instantiated only once and is reused by each test case. ListNode p,q,r,head; if(l1 == null && l2 == null){ return null; } if(l1 == null){ return l2; } if(l2 == null){ return l1; } // if(p == null && q == null){ // return l1; // } p = l1; q = l2; head = null; if(p.val <= q.val){ // r->next = p; head = p; p = p.next; } else{ head = q; q = q.next; // r->next = q; // r-next = p; } r = head; while(p != null && q != null){ if(p.val <= q.val){ // r->next = p; r.next = p; r = p; p = p.next; } else{ r.next = q; r = q; q = q.next; // r->next = q; // r-next = p; } } if(p == null){ while(q != null){ r.next = q; r = q; q = q.next; } } else{ while(p != null){ r.next = p; r = p; p = p.next; } } return head; } }
终于体会到当初上数据结构时候,老师经常提醒的那句话,今天差点把我弄死了。写了半天,一直提示p和q未初始化。