目錄

第一題: 兩數相加

解題思路:

畫圖決議:

代碼實作:

第二題:分隔鏈表

解題思路:

畫圖決議:

代碼實作:

第三題: 奇偶鏈表

解題思路:

畫圖決議:

代碼實作:

第一題: 兩數相加

Leetcode 2:

描述:

給你兩個 非空 的鏈表，表示兩個非負的整數，它們每位數字都是按照 逆序 的方式存盤的，并且每個節點只能存盤 一位 數字，

請你將兩個數相加，并以相同形式回傳一個表示和的鏈表，

你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭，

解題思路:

1.因為回傳時,長度可能會邊長,所以參考一個傀儡節點,讓相加后的值給新的節點,再連接起來

2.因為每個鏈表的節點數的范圍是[1,100],所以不用判斷兩個鏈表沒有節點的情況

3.參考一個pl指向headA,參考一個ps指向headB,pl的數值域為pl.val,ps的數值域為ps.val

4.相加時,>9時,要進位,可以用ret表示進位,即回傳時鏈表的數值域為 (pl.val+ps.val+ret)%10,ret=(pl.val+ps.val+ret)/10;

5.存在不同長度的鏈表,所以可以讓較短鏈表后面的值為0;

6.遍歷結束時,可能還需要進位,所以在遍歷結束后,要考慮是否進位的情況.

畫圖決議:

代碼實作:

class Solution {
    public ListNode addTwoNumbers(ListNode headA, ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;
        //參考一個傀儡節點 當作新頭
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode flg = tmp;
        int ret = 0;
        //pl與ps同時為null時,遍歷結束
        while(pl != null || ps != null){
            //當短鏈表為null時,讓后面的值全為0
            int v1 = pl!=null ? pl.val : 0;
            int v2 = ps!=null ? ps.val : 0;
            int sum = v1 + v2+ ret;
            //求得的val域要mod 10
            tmp.val = sum % 10 ; 
            //sum>9時,ret為1,sum<=9時,ret為0 
            ret = sum / 10;
            //flg為tmp的前驅節點,在遍歷結束時,不需要進位,可以讓他的next域為null
            flg = tmp;
            //new一個新的節點 
            tmp.next = new ListNode(-1);
            tmp = tmp.next;
            //不為空時,指向下一個節點
            if(pl != null) pl = pl.next;
            if(ps != null) ps = ps.next;
        }
        //當ret==0的時候，不用進位了,多余的節點要去掉,所以讓flg.next=null
        if(ret ==0){
            flg.next=null;
        }else{
            //當ret == 1的時候，此時還要進位
            tmp.val = ret;
        }
        return newHead;
    }
}

第二題:分隔鏈表

Leetcode 86:

描述:

給你一個鏈表的頭節點 head 和一個特定值 x ，請你對鏈表進行分隔，使得所有 小于 x 的節點都出現在 大于或等于 x 的節點之前，

你應當 保留 兩個磁區中每個節點的初始相對位置，

解題思路:

1.首先判斷鏈表是否為空,為慷訓傳null

2.創建兩個傀儡節點,headA,headB,讓值小于x的節點連接在headA里,讓大于等于x的節點連接在headB里

3.最后連接兩個鏈表,讓最后一個節點的next域為null

畫圖決議:

代碼實作:

class Solution {
    public ListNode partition(ListNode head, int x) {
        //判斷是否為空為空直接回傳null
        if(head == null) return null;
        //創建兩個傀儡節點，讓＜x的全部在newHeadA，讓>=x的全部在newHeadB
        ListNode newHeadA = new ListNode(-1);
        ListNode newHeadB = new ListNode(-2);
        ListNode cur = newHeadA;
        ListNode tmp = newHeadB;
        //參考一個prev指向頭節點
        ListNode prev = head;
        while(prev != null){
            //<x放入newHeadA
            if(prev.val <x){
                cur.next = prev;
                cur = prev;
            }else{
                //>=x放到newHeadB
                tmp.next = prev;
                tmp = prev;
            }
            prev = prev.next;
        }
        //鏈接兩個鏈表 把尾節點 null
        cur.next = newHeadB.next;
        tmp.next = null;
        return newHeadA.next;    
    }
}

第三題: 奇偶鏈表

Leetcode 328:

描述:

給定一個單鏈表，把所有的奇數節點和偶數節點分別排在一起，請注意，這里的奇數節點和偶數節點指的是節點編號的奇偶性，而不是節點的值的奇偶性，

解題思路:

1.首先判斷鏈表是否為空,為空直接回傳null;

2.參考2個傀儡節點,讓headA存放雙數,headB存放單數(這里是編號的奇偶性)

3.用flg來判斷,第一次進入回圈為單數,第二次為雙數

4.遍歷結束后鏈接兩個鏈表,讓最后一個節點的next域為null;

畫圖決議:

代碼實作:

class Solution {
    public ListNode oddEvenList(ListNode head) {
        //判斷頭結點是否為空，為空直接回傳null
        if(head == null) return null;
        //參考2個傀儡節點，一個存單數，一個存雙數
        ListNode headA = new ListNode(-1);
        ListNode headB = new ListNode(-2);
        //headB單數 headA雙數
        ListNode prev = headA;
        ListNode tmp = headB;
        ListNode cur = head;
        //用flg的值來判斷是否為單數
        int flg = 0;
        while(cur != null){
            //flg==0的時候是 1 3 5 7
            if(flg == 0){
                tmp.next =cur;
                tmp=cur;
                cur=cur.next;
                flg = 1;
            }else{
                //flg == 1 的時候是 2 4 6
                prev.next = cur;
                prev = cur;
                cur = cur.next;
                flg=0;
            }
        }
        //最后鏈接兩個節點 讓tmp.next指向headA.next;
        tmp.next = headA.next;
        //讓prev.next置空
        prev.next = null;
        return headB.next;
    }
}