企業(yè)建立網(wǎng)站需要產(chǎn)品代理推廣方案
每道題后都有解析幫助你分析做題,答案在最下面,關注博主每天持續(xù)更新。
PS:每道題解題方法不唯一,歡迎討論!
1.兩數(shù)相加
題目描述
給你兩個非空的鏈表,表示兩個非負的整數(shù)。它們每位數(shù)字都是按照逆序的方式存儲的,并且每個節(jié)點只能存儲一位數(shù)字。
這兩個數(shù)都不會以 0 開頭。
請你將兩個數(shù)相加,并以相同形式返回一個表示和的鏈表。
示例
輸入: l1 = [1,2,3], l2 = [4,5,6] 輸出:[4,7,9]
輸入:l1 = [1,2],l2 = [9] 輸出:[0,3]
解析
由于鏈表數(shù)字是逆序方式存儲的,所以兩個鏈表對應節(jié)點值可以相加,將它放入新的鏈表中。
但由于每個節(jié)點只能儲存一位數(shù)字,所以兩個節(jié)點相加的值放入時需要(l1.val + v2.val) % 10,創(chuàng)建一個變量carry = (v1.val + l2.val) / 10接受進位值。
在進行下面節(jié)點的時候,carry參與運算,放入新鏈表的值就變成(l1.val + l2.val + carry) % 10, carry = (l2.val + l1.val + carry) / 10。
如果兩個鏈表的長度不同,則可以認為長度短的鏈表的后面有若干個
0。
此外,如果鏈表遍歷結束后,有carry > 0,新鏈表的需要在添加一個值為carry的節(jié)點。
2. 刪除鏈表倒數(shù)第N個節(jié)點
題目描述
給你一個鏈表,刪除鏈表倒數(shù)第N個節(jié)點,并返回鏈表頭節(jié)點。
示例
輸入: head = [1,2,3,4,5],n = 3 輸出: [1,2,4,5]
輸入: head = [1,2,3],n = 3 輸出: [2,3]
輸入: head = [ 1 ],n = 1 輸出: []
解析
不知道你們看到這道題第一想法是什么,我的第一想法就是前后雙指針,使用兩個指針fast和slow一前一后遍歷。
由于要刪除倒數(shù)第n個節(jié)點,所以fast先遍歷,當fast比slow快n個節(jié)點時,兩個指針同時遍歷鏈表。
當fast指針的下一個節(jié)點為null時,slow指針的下個節(jié)點剛好是要刪除的節(jié)點,這個時候只需要將slow.next指向slow.next.next即可。
注意一些特殊情況,當fast指針先走時,fast為null時,說明刪除節(jié)點不存在,返回null;當fast先走完時,fast為null,說明刪除節(jié)點為頭節(jié)點,直接返回頭節(jié)點的下一個節(jié)點。
3. 合并兩個有序列表
題目描述
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
示例
輸入:l1 = [1,3,5], l2 = [1,4,5] 輸出:[1,1,3,4,5,5]
輸入:l1 = [], l2 = [] 輸出:[]
輸入:l1 = [], l2 = [1] 輸出:[1]
解析
這題可以使用遞歸,也可以迭代,就是遍歷兩個鏈表,一個一個比較。
這里我介紹一下遞歸:
如果 l1 或者 l2 一開始就是空鏈表 ,那么沒有任何操作需要合并,所以我們只需要返回非空鏈表。否則,我們要判斷 l1 和 l2 哪一個鏈表的頭節(jié)點的值更小,然后遞歸地決定下一個添加到結果里的節(jié)點,如l1.val < l2.val; l1.next = mergeTwoLists(l1.next,l2);如果兩個鏈表有一個為空,遞歸結束。
答案
1. 兩數(shù)相加
> public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = new ListNode(0);ListNode cur = head;int count = 0;while(l1 != null && l2 != null){cur.next = new ListNode(((l1.val + l2.val + count) % 10));count = (l1.val + l2.val + count) / 10;cur = cur.next;l1 = l1.next;l2 = l2.next;}while(l1 != null){cur.next = new ListNode((l1.val + count) % 10);count = (l1.val + count) / 10;cur = cur.next;l1 = l1.next;}while(l2 != null){cur.next = new ListNode((l2.val + count) % 10);count = (l2.val + count) / 10;cur = cur.next;l2 = l2.next;}if(count > 0){cur.next = new ListNode(count);}return head.next;}
2. 刪除鏈表倒數(shù)第N個節(jié)點
public ListNode removeNthFromEnd(ListNode head, int n) {ListNode slow = head;ListNode fast = head;for(int i = 0;i < n; i++){if(fast == null){return null;}fast = fast.next;}if(fast == null){return head.next;}while(fast.next != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return head;}
3.合并兩個有序列表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null){return list2;}else if(list2 == null){return list1;}else{if(list1.val < list2.val){list1.next = mergeTwoLists(list1.next,list2);return list1;}else{list2.next = mergeTwoLists(list1,list2.next);return list2;}}}