1. 給定x根據(jù)x把鏈表分割,大的結(jié)點放在x后面,小的結(jié)點放在x前面

題目解析:

? ? ? ? 注意此時的pHead就是head(頭節(jié)點的意思)

? ? ? ? 基本上就是給定一個鏈表,我們根據(jù)x的值來把這個鏈表分成倆部分,大的那部分放在x后面,小的那部分放在x前面,并且我們不能改變鏈表本來的順序,比如下面的鏈表,我們先找到的15,就不能把23放在15前面,差不多就是找到一個插一個.

我們定義cur指向當前的head結(jié)點,我們再定義bs,be,as,ae分別代表分割成的倆部分的頭和尾,在一開始,我們cur指向的第一個結(jié)點,我們be和bs或者as,ae都指向第一個結(jié)點.

當我們安置好第一個結(jié)點的時候,我們就開始對后面結(jié)點進行操作,此時我們的as和bs不會動,一直指向第一個結(jié)點,而我們的ae,be就會一直指向最后一個結(jié)點,會不斷的跟新,比如,33大于x,應(yīng)該放在右邊,as.next = cur;as = as.next;因為cur的跟新在if和else都有,因此我們直接合并成一句,放在循環(huán)內(nèi)部,if和eles外部,cur = cur.next;

但是,這里有一個地方,就是我們需要判斷一下極端情況,比如只有一個半?yún)^(qū)的情況也就是下圖.

如果,我們不把ae置空我們就會出現(xiàn)這種情況,我們ae會指向一個結(jié)點,然后形成一個死循環(huán)

整體代碼:

 //TODO ，以給定值x為基準將鏈表分割成兩部分，所有小于x的結(jié)點排在大于或等于x的結(jié)點之前//鏈表分割public ListNode partition(ListNode pHead, int x) {//先判斷pHead是不是nullif (pHead == null) {return null;}//設(shè)置倆個鏈表的開頭和結(jié)尾,分別進行尾插法ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = pHead;//遍歷鏈表while (cur != null) {//判斷cur和x的值if (cur.val < x) {//如果<x那就放在bs和be里面if (bs == null) {//如果是第一個結(jié)點be = cur;bs = cur;} else {//be永遠指向的是最后一個結(jié)點be.next = cur;be = be.next;}} else {//如果<x那就放在bs和be里面if (as == null) {//如果是第一個結(jié)點ae = cur;as = cur;} else {//be永遠指向的是最后一個結(jié)點ae.next = cur;ae = ae.next;}cur = cur.next;}}//但是不一定是有左右倆邊的,可能只有一邊if(bs == null){//第一個區(qū)間沒有數(shù)據(jù)return as;}
//        if(as == null) {
//            //第二個區(qū)間沒有數(shù)據(jù)
//            return bs;
//        }//直接合并為一個//鏈接倆個鏈表,第一個區(qū)間有數(shù)據(jù)be.next = as;//左右都有數(shù)據(jù)的情況,要把ae置為空不然這玩意會報空指針異常if(as != null) {//第二個區(qū)間有數(shù)據(jù)ae.next = null;}return pHead;}

2. 鏈表的回文結(jié)構(gòu)

題目解析:

給我們一個鏈表,我們需要判斷是不是回文鏈表,也是就從中間為界限,從后往前和從前往后對應(yīng)的結(jié)點的val要一致,直到相遇為止.

基本上就是分為倆步驟:1> 找到中間結(jié)點 2> 改變鏈表結(jié)構(gòu)((從中間開始直到最后,讓鏈表翻轉(zhuǎn)) 3> 一次比較倆端的結(jié)點值.

我們先進行第一步,找到中間結(jié)點,我們使用快慢指針來找,fast每次走倆步,slow每次走一步,當退出循環(huán)的時候,slow指向的位置就是中間位置.

我們進入第二步驟,把鏈表進行翻轉(zhuǎn),我們定義cur指向slow的下一個結(jié)點,curNext指向cur的下一個結(jié)點,當cur != null 的時候我們就把cur.next = slow,然后更新slow,slow = cur;再更新cur,cur = curNext;

第三步:從前往后從后往前分別比較,此時我們要考慮偶數(shù)結(jié)點的情況下,我們會產(chǎn)生偶數(shù)個結(jié)點的時候判斷失敗,主要原因和解決方法如圖,我們只要判斷head.next是否和slow指向的結(jié)點相同即可

整體代碼:

????????

public boolean chekPalindrome() {if (head == null || head.next == null) {return true;}ListNode fast = head;ListNode slow = head;//1. 先找到中間位置while (fast != null && fast.next != null) {//注意這里分奇偶節(jié)點數(shù)fast = fast.next.next;//這個可能造成fast后面就是一個null的情況,因此判斷條件不能換,不然會空指針異常slow = slow.next;}//出來之后slow就是中間位置//2. 翻轉(zhuǎn)ListNode cur = slow.next;while (cur != null) {ListNode curNext = cur.next;cur.next = slow;slow = cur;cur = curNext;}//此時slow在最后,不用fast的原因是,當結(jié)點為偶數(shù)個的時候fast會移動到鏈表外面//3. 從前到后,從后到前while (head != slow) {if (head.val != slow.val) {return false;}if (head.next == slow) {return true;//判斷如果是偶數(shù)情況下}head = head.next;slow = slow.next;}return true;}

3. 輸入倆個鏈表,找出它們的第一個公共結(jié)點

題目解析:

? ? ? ? 現(xiàn)在我們有倆個相交鏈表(不為空),我們要找到他們的公共結(jié)點,并且返回公共結(jié)點.如下圖的情況.整體就分為四步:

1. 分別求長度. 2.最長的走差值步. 3. 同時走. 4. 相遇的就是交點

????????因為倆個鏈表的長度我們不確定,因此我們不能夠同時走,然后邊走邊比較.我們應(yīng)該讓長的鏈表先走.此時我們設(shè)置pl和ps分別指向headA和headB.(pl指向的是長的,ps指向的是短的,現(xiàn)在此刻先默認headA是長的),然后我們求出headA和headB鏈表的長度.len1,len2.當pl和ps進行完了遍歷操作之后,他們已經(jīng)走完了鏈表為null了,所以我們需要更新他們,讓他們指向頭.然后我們先讓len=len1-len2,判斷l(xiāng)en是不是大于0,如果大于0,我們就知道headA大于headB,我們就不需要更改pl和ps.如果小于0,我們就需要改變pl和ps的指向,并且讓len = len2-len1;

然后我們讓長的鏈表先走len步,也就是當pl!=null的時候,我們一直讓pl=pl.next;

我們再讓pl和ps指向的鏈表同時走.直到pl==ps為止跳出循環(huán)

但是跳出循環(huán)的條件其實還有一種情況,當pl和ps一樣長并且沒有交點的時候,我們就需要判斷pl==null;如果滿足就返回null

整體代碼:

public ListNode getIntersectionNode(ListNode headA,ListNode headB) {//1.分別求倆個鏈表的長度//pl指向最長的,ps指向最短的ListNode pl = headA;ListNode ps = headB;int len1 = 0;int len2 = 0;while (pl != null) {len1++;pl = pl.next;}while (ps != null) {len2++;ps = ps.next;}//重新到頭pl = headA;ps = headB;int len = len1 - len2;if(len < 0) {pl = headB;ps = headA;len = len2 - len1;}//2.最長的走差值步while (len != 0) {pl = pl.next;len--;}//3.一起走while (pl != ps) {pl = pl.next;ps = ps.next;}//如果鏈表很短,而且一樣長,不會相遇也會跳出循環(huán)if(pl == null) {return null;}return pl;}

4. 給定一個鏈表,判斷鏈表是否有環(huán)

題目解析:

一個鏈表有環(huán),差不多就是下面這個情況,我們的最后一個結(jié)點指向的是前面的結(jié)點,然后形成一個環(huán).

此刻我們使用快慢指針,fast = head;slow = head;每次fast走倆步,slow走一步,只要我們的fast比slow快,先進入環(huán),那么我們的fast和slow一定會在環(huán)里面相遇.

我們while的判定條件不能是fast!=slow;因為如果沒有環(huán)的話,fast會一直往下走,此時到最后一個結(jié)點的時候fast.next.next就會導致空指針異常.我們只能是把fast != null;fast.next != null 作為判定條件,保證沒有環(huán)的情況.

整體代碼:

//TODO 求環(huán)的入口點public ListNode detectCycle () {if (head == null) {return null;}//設(shè)定快慢指針ListNode fast = head;ListNode slow = head;//fast走倆步,slow走一步
//        while (fast != slow) {//TODO 這樣寫會空指針異常
//            fast = fast.next.next;
//            slow = slow.next;
//        }while (fast != null && fast.next != null) {//TODO 這樣寫會空指針異常//有可能為環(huán),有可能為直線fast = fast.next.next;slow = slow.next;if(fast == slow) {//此刻相遇了break;}}//無環(huán)if(fast == null || fast.next == null) {return null;}//有環(huán)slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}

5.給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 NULL

題目解析:

我們要找到開始入環(huán)的第一個結(jié)點如圖

首先找到相遇結(jié)點,這個在第4題就解決了,然后我們更新slow,最后讓slow和fast不斷一直走,直到相遇為止,此時就是入口結(jié)點.

整體代碼:?

//TODO 求環(huán)的入口點public ListNode detectCycle () {if (head == null) {return null;}//設(shè)定快慢指針ListNode fast = head;ListNode slow = head;//fast走倆步,slow走一步while (fast != null && fast.next != null) {//TODO 這樣寫會空指針異常//有可能為環(huán),有可能為直線fast = fast.next.next;slow = slow.next;if(fast == slow) {//此刻相遇了break;}}//無環(huán)if(fast == null || fast.next == null) {return null;}//有環(huán)slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}

? ? ?