當前位置：首頁 > news >正文

網站建設企業(yè) 熊賬號aso優(yōu)化app推廣

news 2025/7/11 23:37:49

網站建設企業(yè) 熊賬號,aso優(yōu)化app推廣,網站建設素材網,專門做電商的網站有哪些JAVA語言編寫 24. 兩兩交換鏈表中的節(jié)點谷歌、亞馬遜、字節(jié)、奧多比、百度給你一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后鏈表的頭節(jié)點。你必須在不修改節(jié)點內部的值的情況下完成本題（即，只能進行節(jié)點交換）?！?article class="baidu_pl">

JAVA語言編寫

24. 兩兩交換鏈表中的節(jié)點

谷歌、亞馬遜、字節(jié)、奧多比、百度

給你一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后鏈表的頭節(jié)點。你必須在不修改節(jié)點內部的值的情況下完成本題（即，只能進行節(jié)點交換）。

示例 1：

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]

示例 2：

輸入：head = []
輸出：[]

示例 3：

輸入：head = [1]
輸出：[1]

提示：

鏈表中節(jié)點的數目在范圍 [0, 100] 內
0 <= Node.val <= 100

教程：https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

視頻：https://www.bilibili.com/video/BV1YT411g7br

方法一：雙指針法

思路：

24.兩兩交換鏈表中的節(jié)點1

操作之后的鏈表：

24.兩兩交換鏈表中的節(jié)點2

復雜度分析：

時間復雜度： $O (n)$
空間復雜度： $O (1)$

class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {public ListNode swapPairs(ListNode head) {ListNode dumyhead = new ListNode(-1); // 設置一個虛擬頭結點dumyhead.next = head; // 將虛擬頭結點指向head，這樣方面后面做刪除操作ListNode cur = dumyhead;ListNode temp; // 臨時節(jié)點，保存兩個節(jié)點后面的節(jié)點ListNode firstnode; // 臨時節(jié)點，保存兩個節(jié)點之中的第一個節(jié)點ListNode secondnode; // 臨時節(jié)點，保存兩個節(jié)點之中的第二個節(jié)點while (cur.next != null && cur.next.next != null) {temp = cur.next.next.next;firstnode = cur.next;secondnode = cur.next.next;cur.next = secondnode;       // 步驟一secondnode.next = firstnode; // 步驟二firstnode.next = temp;      // 步驟三cur = firstnode; // cur移動，準備下一輪交換}return dumyhead.next;}
}

19. 刪除鏈表的倒數第 N 個結點

字節(jié)跳動、亞馬遜、Facebook

給你一個鏈表，刪除鏈表的倒數第 n 個結點，并且返回鏈表的頭結點。

示例 1：

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

示例 2：

輸入：head = [1], n = 1
輸出：[]

示例 3：

輸入：head = [1,2], n = 1
輸出：[1]

提示：

鏈表中結點的數目為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

**進階：**你能嘗試使用一趟掃描實現嗎？

教程：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html

視頻：https://www.bilibili.com/video/BV1vW4y1U7Gf

方法一：自己寫的

思路：很簡單的方法，首先寫一個循環(huán)遍歷head，獲得當前val的個數size。根據倒數第n個數、與size及正著數的索引的關系：flag=size-n+1，刪除結點。對于特殊情況，head為null，則返回空。若刪除是頭結點，也就是n=size的時候，直接返回head.next。

復雜度分析：

時間復雜度： $O (n)$
空間復雜度： $O (1)$

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {
if (head==null) return null;int size=0;ListNode cur = head;ListNode temp=head;ListNode pre = new ListNode(0,temp);while(cur!=null){cur = cur.next;size++;//計算當前ListNode的個數}if(n==size) return head.next;//如果是刪第一個的話，就返回head.nextint flag=0;//記錄索引位置while(temp!=null){//temp是遍歷的if(flag==size-n){//size-n是正數的索引前一個pre.next=temp.next;//刪除操作}flag++;temp=temp.next;pre=pre.next;}return head;}
}

160. 相交鏈表

字節(jié)跳動

給你兩個單鏈表的頭節(jié)點 headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點。如果兩個鏈表沒有交點，返回 null 。

圖示兩個鏈表在節(jié)點 c1 開始相交**：**

題目數據保證整個鏈式結構中不存在環(huán)。

注意，函數返回結果后，鏈表必須 保持其原始結構 。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。
在 A 中，相交節(jié)點前有 2 個節(jié)點；在 B 中，相交節(jié)點前有 3 個節(jié)點。

示例 2：

輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點前有 3 個節(jié)點；在 B 中，相交節(jié)點前有 1 個節(jié)點。

示例 3：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null 。

提示：

listA 中節(jié)點數目為 m
listB 中節(jié)點數目為 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 沒有交點，intersectVal 為 0
如果 listA 和 listB 有交點，intersectVal == listA[skipA + 1] == listB[skipB + 1]

**進階：**你能否設計一個時間復雜度 O(n) 、僅用 O(1) 內存的解決方案？

教程：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html

方法一：

思路：求出兩個鏈表的長度，并求出兩個鏈表長度的差值，然后讓curA移動到，和curB 末尾對齊的位置，比較curA和curB是否相同，如果不相同，同時向后移動curA和curB，如果遇到curA == curB，則找到交點。否則循環(huán)退出返回空指針。

復雜度分析：

時間復雜度： $O (n A + n B)$ ,nA是鏈表A的長度,nB是鏈表B的長度
空間復雜度： $O (1)$

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0, lenB = 0;while (curA != null) { // 求鏈表A的長度lenA++;curA = curA.next;}while (curB != null) { // 求鏈表B的長度lenB++;curB = curB.next;}curA = headA;curB = headB;// 讓curA為最長鏈表的頭，lenA為其長度if (lenB > lenA) {//1. swap (lenA, lenB);int tmpLen = lenA;lenA = lenB;lenB = tmpLen;//2. swap (curA, curB);ListNode tmpNode = curA;curA = curB;curB = tmpNode;}// 求長度差int gap = lenA - lenB;// 讓curA和curB在同一起點上（末尾位置對齊）while (gap-- > 0) {curA = curA.next;}// 遍歷curA 和 curB，遇到相同則直接返回while (curA != null) {if (curA == curB) {return curA;}curA = curA.next;curB = curB.next;}return null;}}

142. 環(huán)形鏈表 II

字節(jié)跳動、谷歌 Google、Facebook

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

如果鏈表中有某個節(jié)點，可以通過連續(xù)跟蹤 next 指針再次到達，則鏈表中存在環(huán)。為了表示給定鏈表中的環(huán)，評測系統(tǒng)內部使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。注意：pos 不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改 鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節(jié)點
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環(huán)。

提示：

鏈表中節(jié)點的數目范圍在范圍 [0, 104] 內
-105 <= Node.val <= 105
pos 的值為 -1 或者鏈表中的一個有效索引

**進階：**你是否可以使用 O(1) 空間解決此題？

教程：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

視頻：https://www.bilibili.com/video/BV1if4y1d7ob/

方法一：

思路：可以使用快慢指針法，分別定義 fast 和 slow 指針，從頭結點出發(fā)，fast指針每次移動兩個節(jié)點，slow指針每次移動一個節(jié)點，如果 fast 和 slow指針在途中相遇，說明這個鏈表有環(huán)。

復雜度分析：

時間復雜度： $O (n)$
空間復雜度： $O (1)$

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 有環(huán)ListNode index1 = fast;ListNode index2 = head;// 兩個指針，從頭結點和相遇結點，各走一步，直到相遇，相遇點即為環(huán)入口while (index1 != index2) {index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}