---

翻轉(zhuǎn)鏈表

    //反轉(zhuǎn)鏈表//實質(zhì)上是把每一個節(jié)點頭插法,原本第一個節(jié)點變成最后一個節(jié)點public ListNode reverseList(){//鏈表為空if (head == null){return null;}//鏈表只有一個節(jié)點if (head.next == null ){return head;}ListNode cur = this.head.next;//先定義cur的位置this.head.next =null;//再把head.next置為空while(cur != null){ListNode curNext =cur.next;//再定義curNext在cur后面cur.next =this.head;//讓cur的下一個等于頭節(jié)點，就能把cur頭插到head前面head = cur;//head給到curcur = curNext;//cur再到curNext位置}return head;//返回頭，就能返回一整個鏈表}
}

找到鏈表的中間節(jié)點

方法1：鏈表長度除以2得到中間節(jié)點

    //求鏈表中間節(jié)點//1.先求整個鏈表的長度//2.再求長度/2 就找到這個節(jié)點了public ListNode MiddleNode(){ListNode cur = this.head;int len = size();//讓cur走到中間節(jié)點for (int i = 0; i < len/2; i++) {cur = cur.next;}return cur;}

方法2：
優(yōu)化代碼：快慢指針的引用

1. 當fast == null時，遍歷結(jié)束

2. 當fast.next == null時，遍歷結(jié)束

所以循環(huán)結(jié)束有兩個條件：fast == null 或者 fast.next == null

    public ListNode MiddleNode1(){ListNode fast = this.head;ListNode slow = this.head;while (fast != null && fast.next != null ){fast = fast.next.next;slow = slow.next;}return slow;}

返回倒數(shù)第k個節(jié)點

    public ListNode findKthToTail(int k){//判斷k的合法性if (k <= 0 || head == null){return null;}ListNode fast =head;ListNode slow =head;//先讓fast走k-1步while(k-1 != 0){fast = fast.next;//如果k很大，這個判斷可以讓代碼更高效if (fast == null){return null;}k--;}//slow和fast同時走//當fast.next =null時，slow已經(jīng)在倒數(shù)第k個節(jié)點了while(fast.next != null){fast = fast.next;slow = slow.next;}return slow;}

合并兩個有序鏈表

public class Test {//定義兩個鏈表public static MySingleList.ListNode  mergeTwoLists(MySingleList.ListNode head1, MySingleList.ListNode head2){//定義一個虛擬節(jié)點，保存合并之后的新鏈表MySingleList.ListNode newH = new MySingleList.ListNode(-1);//newH節(jié)點是新鏈表的頭節(jié)點，跟著記錄串聯(lián)之后的節(jié)點MySingleList.ListNode tmpH = newH;//當兩個鏈表都不為空才能進入循環(huán)進行合并排序while(head1 != null && head2 != null){//當head1的值小于head2時，頭節(jié)點tmpH的下一個節(jié)點就是連接小的那一個，然后head1再往后走一步           if (head1.val < head2.val){tmpH.next = head1;head1 = head1.next;}else{//當head2的值小于head1時，頭節(jié)點tmpH的下一個節(jié)點就是連接小的那一個，然后head2再往后走一步  tmpH.next = head2;head2 = head2.next;}//無論進入那個語句，tmp都會往后走一步tmpH = tmpH.next;}//當head1沒走完了，說明head2走完了，繼續(xù)接著剩下的head1if(head1 != null){tmpH.next = head1;}//當head2沒走完了，說明head1走完了，繼續(xù)接著剩下的head2if(head2 != null){tmpH.next = head2;}//最后返回return tmpH;}public static void main(String[] args) {MySingleList mySingleList = new MySingleList();mySingleList.addLast(12);mySingleList.addLast(23);mySingleList.addLast(34);mySingleList.addLast(45);mySingleList.display();//打印數(shù)組MySingleList mySingleList2 = new MySingleList();mySingleList2.addLast(15);mySingleList2.addLast(24);mySingleList2.addLast(37);mySingleList2.addLast(166);mySingleList2.display();MySingleList.ListNode head = mergeTwoLists(mySingleList.head,mySingleList2.head);mySingleList.display();}

判斷鏈表是否回文

1.先找到中間節(jié)點
2.翻轉(zhuǎn)
3.前面往后走，后面往前走，值是否一樣

    //判斷是否回文public boolean chkPalindrome(){ListNode fast = head;ListNode slow = head;int len = size()/2;//5/2=2//1.找中間位置while(fast != null && fast.next != null){//fast先走倆步，slow再走一步fast = fast.next.next;slow = slow.next;}//2.翻轉(zhuǎn)ListNode cur = slow.next;while(cur != null){ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}//3.從前到后，從后到前while(head != slow){if (head.val != slow.val){return false;}//考慮偶數(shù)鏈表if (head.next == slow){return true;}head = head.next;slow = slow.next;}return true;}

注意

在寫題過程中，我混淆了找中間節(jié)點和返回倒數(shù)第k個節(jié)點的方法

他們的區(qū)別其實是：
找中間節(jié)點 ：fast永遠是slow的二倍，slow走一步，fast就走兩步。

返回倒數(shù)第k個節(jié)點 ：fast和slow的關(guān)系不是固定的，fast走幾步根據(jù)k-1得到，還有一個區(qū)別是，fast走了k-1步之后，slow走一步，fast也是走一步。