一、鏈表中倒數(shù)時第k個節(jié)點：

1、題目：

輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。

2、解題思路：單鏈表具有單向移動的特性。

（1）第一種：先遍歷鏈表，算出鏈表節(jié)點數(shù)count，第二次直接遍歷到第count-k個節(jié)點。但是要注意，可能鏈表節(jié)點數(shù)count小于k，此時要返回NULL，所以要先判斷這個條件。（這一種就不貼代碼出來了）

（2）第二種：

可以用兩個指針，一個指針遍歷到第k個結(jié)點的時候，第二個指針再走到第一個節(jié)點，然后兩個指針的距離始終保持k-1，這樣，當(dāng)?shù)谝粋€指針的next==NULL，也就是走到最后一個節(jié)點的時候，第二個指針對應(yīng)的位置，就是倒數(shù)第k個結(jié)點。

這樣的好處是能夠節(jié)省一個循環(huán)，時間復(fù)雜度會相應(yīng)降低。從Q(2N) 到Q(N)

注意，但是需要一個小循環(huán)讓第一個指針先走到第k個指針。同時也存在結(jié)點總數(shù)小于k的問題，如果循環(huán)還沒有進行到k次，而第一個指針的已經(jīng)是NULL，即走到頭了，那么，函數(shù)返回NULL。

3、代碼實現(xiàn)：

/* public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;} }*/ public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if(head ==null || k<=0){return null;}ListNode last=head;//第一個指針先移動k-1個節(jié)點for(int i=0;i<k-1;i++){if(head.next!=null){head=head.next;}else{return null;}}//同時移動兩個指針，當(dāng)?shù)谝粋€指針指向null的時候，last就是所求的結(jié)點while(head.next!=null){head=head.next;last=last.next;}return last;} }

?

?

二、反轉(zhuǎn)鏈表：

參考博客：https://www.jianshu.com/p/e385d9c06672

1、題目：

輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。

2、解題思路：

2-1：第一種：使用遞歸方式：

（1）解題思路：

假設(shè)鏈表為[1,2,3,4,5]先迭代到鏈表末尾5，然后從5開始依次反轉(zhuǎn)整個鏈表。
如下圖所示，先迭代待最后一位5，并且設(shè)置一個新的節(jié)點newList作為反轉(zhuǎn)后鏈表的頭結(jié)點，由于整個鏈表反轉(zhuǎn)后的頭就是最后一個數(shù)，所以newList存放的一直是反轉(zhuǎn)后的頭結(jié)點的地址，將head指向的地址賦值給head->next->next指針，并且一定要記得讓head->next =NULL，也就是斷開現(xiàn)在指針的鏈接，否則新的鏈表形成了環(huán)，下一層head->next->next賦值的時候會覆蓋后續(xù)的值。依次反轉(zhuǎn)。。

（2）代碼實現(xiàn)：

/* public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;} }*/ public class Solution {public ListNode ReverseList(ListNode head) {//遞歸方式if(head==null || head.next==null){return head;}ListNode newList=ReverseList(head.next);head.next.next=head;head.next=null;return newList;} }

?

2-2第二種：使用迭代方式：

（1）解題思路：

先給定一個空的鏈表newList，然后判斷傳入的鏈表head是不是空鏈表或者鏈表元素只有一個，如果是，直接返回就可以。如果不是，則對鏈表進行迭代，然后給一個臨時變量temp存儲head.next,然后改變head.next的指向newList,然后把head賦值給newList,接著讓head等于臨時變量temp，就這樣一直迭代完整個鏈表，返回newList就可以。如下圖所示：

（2）代碼實現(xiàn)：

public ListNode ReverseList(ListNode head) {//非遞歸方式：ListNode newList=null;if(head==null || head.next==null){return head;}while(head!=null){ListNode temp=head.next;head.next=newList;newList=head;head=temp;}return newList;}

?

?

三、合并兩個排序的鏈表：

參考博客：https://blog.csdn.net/qq_23217629/article/details/51730312

1、題目：

輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。

2、解題思路：

比較兩個鏈表的第一個節(jié)點，取出最小值的節(jié)點，接著再按照相同的方式重復(fù)比較剩余鏈表的節(jié)點。

3、代碼實現(xiàn)：

public class Solution {public ListNode Merge1(ListNode list1, ListNode list2) {//遞歸版本ListNode head;if (list1 == null) {return list2;}if (list2 == null) {return list1;}if (list1.val < list2.val) {head = list1;head.next = Merge(list1.next, list2);} else {head = list2;head.next = Merge(list1, list2.next);}return head;}public ListNode Merge(ListNode list1,ListNode list2) {//非遞歸版本：ListNode head = new ListNode(-1);//頭節(jié)點，用來存儲合并的鏈表head.next = null;ListNode root = head;//root暫存我新建的頭節(jié)點，合并之后返回root.next，就是題目給的頭節(jié)點while(list1!=null && list2!=null){if(list1.val <=list2.val){head.next=list1;head = list1;list1 = list1.next;}else{head.next=list2;head=list2;list2=list2.next;}}//把未結(jié)束的鏈表連接到合并后的鏈表尾部if(list1 !=null){head.next=list1;}if(list2 !=null){head.next=list2;}return root.next;} }

?

總結(jié)

以上是生活随笔為你收集整理的《剑指offer》-- 链表中倒数第k个节点、反转链表、合并两个排序的链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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