麻豆香蕉品麻豆,无产视频一区二区

LeetCode 160.相交鏈表

編寫一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。
如下面的兩個(gè)鏈表：

示例

在節(jié)點(diǎn) c1 開始相交。
示例 1：

示例1

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。
注意：
如果兩個(gè)鏈表沒有交點(diǎn)，返回 null.
在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。
可假定整個(gè)鏈表結(jié)構(gòu)中沒有循環(huán)。
程序盡量滿足 O(n) 時(shí)間復(fù)雜度，且僅用 O(1) 內(nèi)存。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//令兩個(gè)指針分別指向兩個(gè)鏈表的頭，然后依次往后遍歷，當(dāng)一個(gè)鏈表遍歷至尾時(shí)，令指針指向另一鏈表的頭。
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        while(l1 != l2){
            l1 = (l1 == null) ? headB : l1.next;
            l2 = (l2 == null) ? headA : l2.next;
        }
        return l1;
    }
}

LeetCode 21.合并兩個(gè)有序鏈表

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

/**
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);//創(chuàng)建一個(gè)新鏈表用于保存合并后的結(jié)果
        ListNode curr = result;//創(chuàng)建一個(gè)指向結(jié)果鏈表頭結(jié)點(diǎn)的指針，用于執(zhí)行歸并操作
        while(l1 != null && l2 != null){  //如果l1和l2都還有元素
            if(l1.val < l2.val){  //如果l1元素較小，插入結(jié)果鏈表，兩個(gè)鏈表都進(jìn)行后移
                curr.next = l1;
                curr = curr.next;
                l1 = l1.next;
            }else{
                curr.next = l2;
                curr = curr.next;
                l2 = l2.next;
            }
        }
        if(l1 == null){   
            curr.next = l2;  //如果l2已經(jīng)無元素，則插入l1剩余元素
        }else{
            curr.next = l1;
        }
        return result.next;
    }
}

LeetCode 328.奇偶鏈表

給定一個(gè)單鏈表，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請注意，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號的奇偶性，而不是節(jié)點(diǎn)的值的奇偶性。
請嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時(shí)間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點(diǎn)總數(shù)。
示例 1:
輸入:1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
示例 2:
輸入: 2->1->3->5->6->4->7->NULL
輸出: 2->3->6->7->1->5->4->NULL
說明:
應(yīng)當(dāng)保持奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)的相對順序。
鏈表的第一個(gè)節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)，第二個(gè)節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)，以此類推。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode odd = head; //奇指針指向鏈表頭
        ListNode even = head.next; //偶指針指向鏈表頭指向的下一個(gè)元素(第一個(gè)偶數(shù)對象)
        ListNode evenHead = even; //保存對應(yīng)的偶數(shù)節(jié)點(diǎn)
        while(even != null && even.next != null){
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead; //再把奇偶連接起來
        return head;
    }
}

LeetCode 206.反轉(zhuǎn)鏈表

反轉(zhuǎn)一個(gè)單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null||head.next == null){
            return head;
        }
        ListNode p = head;
        ListNode newH = null;
        while(p!=null){
            ListNode temp = p.next;
            p.next = newH;
            newH = p;
            p = temp;
    }  
        return newH;
    }
}

LeetCode 19.刪除鏈表中的倒數(shù)第N個(gè)節(jié)點(diǎn)

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.
說明：
給定的 n 保證是有效的。
進(jìn)階：
你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast_p = dummy;
        ListNode slow_p = dummy;
        for(int i = 0; i < n + 1; i++){
            fast_p = fast_p.next;
        }
        while(fast_p != null){
            fast_p = fast_p.next;
            slow_p = slow_p.next;
        }
        slow_p.next = slow_p.next.next;
        return dummy.next;
    }
}

LeetCode 445.兩數(shù)相加②

給定兩個(gè)非空鏈表來代表兩個(gè)非負(fù)整數(shù)。數(shù)字最高位位于鏈表開始位置。它們的每個(gè)節(jié)點(diǎn)只存儲單個(gè)數(shù)字。將這兩數(shù)相加會返回一個(gè)新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會以零開頭。
進(jìn)階:
如果輸入鏈表不能修改該如何處理？換句話說，你不能對列表中的節(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)。
示例:
輸入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出: 7 -> 8 -> 0 -> 7

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> l1_Stack = LinkListToStack(l1);
        Stack<Integer> l2_Stack = LinkListToStack(l2);
        int carry = 0;
        ListNode head = new ListNode(-1);
        while(!l1_Stack.isEmpty() || !l2_Stack.isEmpty() || carry != 0){
            int l1_val = l1_Stack.isEmpty() ? 0 : l1_Stack.pop();
            int l2_val = l2_Stack.isEmpty() ? 0 : l2_Stack.pop();
            int sum = l1_val + l2_val + carry;
            ListNode node = new ListNode(sum % 10);
            node.next = head.next;
            head.next = node;
            carry = sum / 10;
        }
        return head.next;
    }
    private Stack<Integer> LinkListToStack(ListNode l) {
        Stack<Integer> stack = new Stack<>();
        while(l != null){
            stack.push(l.val);
            l = l.next;
        }
        return stack;
    }
}

LeetCode 2.兩數(shù)相加

給出兩個(gè) 非空的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照逆序的方式存儲的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲一位數(shù)字。
如果，我們將這兩個(gè)數(shù)相加起來，則會返回一個(gè)新的鏈表來表示它們的和。
您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會以 0 開頭。
示例：
輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0);
        ListNode temp = result;
        int sum = 0;
        while(l1!=null || l2!= null){
            if(l1!= null){
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2!= null){
                sum += l2.val;
                l2 = l2.next;
            }
            temp.next = new ListNode(sum % 10);
            temp = temp.next;
            sum = sum / 10;
        }
        if(sum != 0){
            temp.next = new ListNode(1);
        }
        return result.next;
    }
}

LeetCode 234.回文鏈表

請判斷一個(gè)鏈表是否為回文鏈表。
示例 1:
輸入:1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進(jìn)階：
你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    //使用快慢指針找到鏈表的中段。
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null){
            return true;
        }
        
        ListNode slow_p = head;
        ListNode fast_p = head.next;
        while(fast_p != null && fast_p.next != null){
            slow_p = slow_p.next;
            fast_p = fast_p.next.next;
        }
        if(fast_p != null){
            slow_p = slow_p.next;
        }
        cut(head,slow_p);
        return isEqual(head,reverse(slow_p));
    }
    
    //剪切鏈表讓其劃分為兩段
    private void cut(ListNode head,ListNode cutNode){
        while(head.next != cutNode){
            head = head.next;
        }
        head.next = null;
    }
    
    //翻轉(zhuǎn)鏈表
    private ListNode reverse(ListNode head){
        ListNode newH = null;
       
        while(head != null){
            ListNode temp = head.next;
            head.next = newH;
            newH = head;
            head = temp;
        }
        return newH;
    }
    
    //判斷鏈表是否回文
    private boolean isEqual(ListNode l1,ListNode l2){
        while(l1 != null && l2 != null){
            if(l1.val != l2.val){
                return false;
            }
            l1 = l1.next;
            l2 = l2.next;
        }
        return true;
    }
}

LeetCode 83.刪除排序鏈表中的重復(fù)元素

給定一個(gè)排序鏈表，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while(current != null && current.next != null){
            if(current.val == current.next.val){
                current.next = current.next.next;
            }else{
                current = current.next;
            }
        }
        return head;
    }
}

LeetCode 19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.
說明:
給定的 n 保證是有效的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast_p = dummy;
        ListNode slow_p = dummy;
        for(int i = 0; i < n + 1; i++){
            fast_p = fast_p.next;
        }
        while(fast_p != null){
            fast_p = fast_p.next;
            slow_p = slow_p.next;
        }
        slow_p.next = slow_p.next.next;
        return dummy.next;
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LeetCode | 鏈表相關(guān)題目

LeetCode | 鏈表相關(guān)題目

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

LeetCode | 鏈表相關(guān)題目

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av