面試題17：合并兩個有序鏈表

這道題用遞歸，很容易實現(xiàn)，但是一定要注意代碼魯棒性

下面是源碼：

public static ListNode MergeList(ListNode head1,ListNode head2){ListNode newHead = null;if(head1==null){return head2;}else{if(head2==null){return head1;}}if(head1.val<head2.val){newHead = head1;newHead.next = MergeList(head1.next,head2);}if(head1.val>head2.val){newHead = head2;newHead.next = MergeList(head1,head2.next);}return newHead;}

　　通過這道題想到如果是有序數(shù)組的話，該如何合并，這里不能用遞歸，主要是因為數(shù)組長度的問題

可以借鑒劍指offer第4題，替換空格。源碼就不賦了，之前的博客中有提到過。

面試題15：鏈表中的倒數(shù)第K 個結(jié)點

當(dāng)一個指針無法解決問題的時候，考慮嘗試兩個或三個指針，同樣求鏈表的中間結(jié)點以及判斷單向鏈表是否有環(huán)都可以考慮使用兩個指針。

這道題可以考慮兩個指針，一個在前，另一個在他K-1的位置，但是要注意如果k 為0，頭結(jié)點為空，或者鏈表長度小于K，這些情況

下面附上程序的源代碼：

public static ListNode findKNode(ListNode head, int k){if(head==null||k == 0){return null;}ListNode p1 = head;ListNode p2 = head;for(int i =0;i<k-1;i++){if(p1.next!=null){p1 = p1.next;}else{return null;}}while(p1.next!=null){p1 = p1.next;p2 = p2.next;}return p2;}

　面試題16：翻轉(zhuǎn)鏈表

　這道題用到了三個指針，只要保證翻轉(zhuǎn)的時候鏈表不斷就可以.

這道題也是leetcode上top10的題目；

Reverse Linked List

?Reverse a singly linked list.

下面附上代碼：

public ListNode reverseList(ListNode head) {ListNode n = head;ListNode l = null;ListNode r = null;ListNode newHead = null;while(n!=null){r = n.next;if(r==null){newHead = n;}n.next = l;l = n;n = r;}return newHead;}

　　

?

轉(zhuǎn)載于:https://www.cnblogs.com/gracyandjohn/p/4549412.html

總結(jié)

以上是生活随笔為你收集整理的剑指offer之链表续的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。