1、鏈表相加

題目

給定兩個鏈表，分別表示兩個非負(fù)整數(shù)，逆序存儲在鏈表中，計算兩個數(shù)的和，并返回鏈表頭指針，如：
輸入：２－＞４－＞３、５－＞６－＞４，輸出７－＞０－＞８

思路及代碼

• 常規(guī)思路：考慮到鏈表可能是不等長的，所以先將鏈表反轉(zhuǎn)，這樣就可以對應(yīng)位置直接相加，注意考慮進位，代碼：

public class solution{
    public ListNode addTwoNumber(ListNode l1, ListNode l2){
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode sumReverseList = addTwoNumbersReversed(l1, l2);
        reverseList(l1);
        reverseList(l2);
        return reverseList(sumReversed);
    }
    
    public ListNode addTwoNumbersReversed(ListNode l1, ListNode l2){
        ListNode head = new ListNode(0);
        ListNode curr = head;
        int carry = 0;
        while(l1 != null || l2 != null || carry == 1){
            int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
            if(sum > 9){
                carry = 1;
                sum /= 10;
            }
            else{
                carry = 0;
            }
            curr.next = new ListNode(sum);
            curr = curr.next;
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }
        return head.next;
    }

    public ListNode reverseList(ListNode head){
        ListNode curr = head;
        ListNode next;
        ListNode prev = null;
        while(curr != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

• 遞歸版本：

public class solution{
    public ListNode addTwoNumbers(ListNode l1, ListNode l2){
        if(l1 == null || l2 == null){
            return l1 == null ? l2 : l1;
        }
        return addTwoNumbers_3(l1, l2, 0);
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2, int carry){
        if(l1 == null && l2 == null){
            return carry == 0 ? null : new ListNode(1);
        }
        int num1 = l1 == null ? 0 : l1.val;
        int num2 = l2 == null ? 0 : l2.val;
        boolean flag = false;
        int sum = num1 + num2 + carry;
        if(sum > 9){
            flag = true;
            sum = sum - 10;
        }
        ListNode res = new ListNode(sum);
        res.next = addTwoNumbers_3(l1 == null ? l1 : l1.next, l2 == null ? l2 : l2.next, flag ? 1 : 0);
        return res;
    }
}

• 堆棧版本：首先將list都放入stack中,再進行操作

public class solution{
    public ListNode addTwoNumbers_1(ListNode l1, ListNode l2){
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s2 = new Stack<Integer>();

        while(s1 != null){
            s1.push(l1.val);
            l1 = l1.next;
        }
        while(s2 != null){
            s2.push(l2.val);
            l2 = l2.next;
        }

        int sum = 0;
        ListNode list = new ListNode(0);
        while(!s1.empty() || !s2.empty()){
            if(!s1.empty()){
                sum += s1.pop();
            }
            if(!s2.empty()){
                sum += s2.pop();
            }
            list.val = sum % 10;
            ListNode head = new ListNode(sum / 10);
            // 此處是關(guān)鍵, 將head賦值給list,即list是不斷的增加頭部節(jié)點
            // 每次產(chǎn)生的head作為頭部添加到list中
            head.next = list;
            list = head;
            sum /= 10;
        }
        return list.val == 0 ? list.next : list;
    }
}

2、鏈表反轉(zhuǎn)

題目

給定一個鏈表，反轉(zhuǎn)該鏈表從m位置到n位置，要求直接反轉(zhuǎn)不申請額外空間
如給定1 - >2 - >3 - >4 - >5，m=2，n =4，返回1 - >4 - >3 - >2 - >5

思路及代碼

• 全部翻轉(zhuǎn)，使用遞歸

public ListNode reverseList(ListNode node){
    if(node == null || node.next == null){
        return node;
    }
    ListNode preNode = reverseList(node.next);
    node.next.next = node; #反轉(zhuǎn)
    node.next = null;
    return preNode;
}

• 全部翻轉(zhuǎn)，使用循環(huán)

public listNode reverseList(ListNode node){
    if(node == null){
        return null;
    }
    ListNode pre = null;
    ListNode next = null;
    while(node!=null){
        # 避免斷裂，先將后邊的數(shù)據(jù)存入next
        next = node.next;
        # 將當(dāng)前節(jié)點指向前節(jié)點
        node.next = pre;
        # 將當(dāng)前節(jié)點和前一節(jié)點向后移一位
        pre = node;
        node = next;
    }
    return pre;
}

• 部分翻轉(zhuǎn)

  
  
  reverseList示意圖

public class solution{
    public ListNode reverseList(ListNode head, int from, int to){
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        // 定義curr節(jié)點，從prehead開始，找到第m-1個節(jié)點，作為curPre
        ListNode curr = preHead;
        for(int i = 1; i < from; i++){
            curr = curr.next;
        }
        ListNode curPre = curr;
        curr = curr.next;
        ListNode curNext = null;
        for(int i=from; i<to; i++){
            curNext = curr.next;
            curr.next = curNext.next;
            curNext.next = curPre.next;
            curPre.next = curNext;
        }
        return preHead.next;
    }
}

鏈表去重，待補充...

題目

給定排序的鏈表，刪除重復(fù)的節(jié)點，只保留重復(fù)元素第一次出現(xiàn)的節(jié)點，如：
給定：2->3->3->5->7->8->8->8->9->9->10
返回：2->3->5->7->8->9->10

思路及代碼

若p.next的值與p相等，則將p.next.next指向p，刪除p.next，重復(fù)此過程，至鏈表尾端

鏈表劃分

題目

給定一個鏈表和一個值x，將鏈表劃分成兩部分，使得劃分后小于x的節(jié)點在前，大于x的節(jié)點在后，且保持原鏈表中出現(xiàn)的順序不變，如：
給定1->4->3->2->5->2和x=3，返回1->2->2->4->3->5

思路及代碼

鏈表公共節(jié)點

題目

給定兩個單向鏈表，計算兩個鏈表的第一個公共節(jié)點，若沒有返回空

思路及代碼