概述
本文是從leetcode題庫中精選出的關(guān)于鏈表的題目，在面試中具有較高的出現(xiàn)頻率。
160. 相交鏈表
編寫一個程序，找到兩個單鏈表相交的起始節(jié)點。
如下面的兩個鏈表：
在節(jié)點 c1 開始相交。
示例 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é)點的值為 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
輸出：Reference of the node with value = 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。
注意：
如果兩個鏈表沒有交點，返回 null.
在返回結(jié)果后，兩個鏈表仍須保持原有的結(jié)構(gòu)。
可假定整個鏈表結(jié)構(gòu)中沒有循環(huán)。
程序盡量滿足 O(n) 時間復(fù)雜度，且僅用 O(1) 內(nèi)存。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode curA = headA;
ListNode curB = headB;
while (curA != curB) {
curA = curA == null ? headB : curA.next;
curB = curB == null ? headA : curB.next;
}
return curA;
}
}
206. 反轉(zhuǎn)鏈表
反轉(zhuǎn)一個單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？
class Solution {
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while (head != null){
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
}
21. 合并兩個有序鏈表
將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}else if (l2 == null) {
return l1;
} else if (l1.val > l2.val) {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
} else{
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
}
}
83. 刪除排序鏈表中的重復(fù)元素
給定一個排序鏈表，刪除所有重復(fù)的元素，使得每個元素只出現(xiàn)一次。
示例 1:
輸入: 1->1->2
輸出: 1->2
示例 2:
輸入: 1->1->2->3->3
輸出: 1->2->3
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur != null && cur.next != null){
if(cur.next.val == cur.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}
19. 刪除鏈表的倒數(shù)第N個節(jié)點
給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點，并且返回鏈表的頭結(jié)點。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
說明：
給定的 n 保證是有效的。
進階：
你能嘗試使用一趟掃描實現(xiàn)嗎？
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode slow = head;
ListNode fast = head;
while(n > 0 && fast != null){
fast = fast.next;
n--;
}
if(fast == null){
return n == 0 ? head.next:head;
}
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}
24. 兩兩交換鏈表中的節(jié)點
給定一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表。
你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換。
示例:
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
class Solution {
public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode firstNode = head;
ListNode secondNode = head.next;
firstNode.next = swapPairs(secondNode.next);
secondNode.next = firstNode;
return secondNode;
}
}
445. 兩數(shù)相加 II
給定兩個非空鏈表來代表兩個非負整數(shù)。數(shù)字最高位位于鏈表開始位置。它們的每個節(jié)點只存儲單個數(shù)字。將這兩數(shù)相加會返回一個新的鏈表。
你可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)字都不會以零開頭。
進階:
如果輸入鏈表不能修改該如何處理？換句話說，你不能對列表中的節(jié)點進行翻轉(zhuǎn)。
示例:
輸入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出: 7 -> 8 -> 0 -> 7
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
LinkedList<Integer> stackA = buildStack(l1);
LinkedList<Integer> stackB = buildStack(l2);
int carry = 0;
ListNode head = new ListNode(-1);
while (!stackA.isEmpty() || !stackB.isEmpty() || carry != 0) {
int x = stackA.isEmpty() ? 0 : stackA.pop();
int y = stackB.isEmpty() ? 0 : stackB.pop();
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
node.next = head.next;
head.next = node;
carry = sum / 10;
}
return head.next;
}
private LinkedList<Integer> buildStack(ListNode head) {
LinkedList<Integer> stack = new LinkedList<>();
while (head != null) {
stack.push(head.val);
head = head.next;
}
return stack;
}
}
234. 回文鏈表
請判斷一個鏈表是否為回文鏈表。
示例 1:
輸入: 1->2
輸出: false
示例 2:
輸入: 1->2->2->1
輸出: true
進階：
你能否用 O(n) 時間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題？
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null){
return true;
}
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null){
slow = slow.next;
}
cut(head, slow);
return isEqual(head, reverse(slow));
}
private void cut(ListNode head, ListNode cutNode) {
while (head.next != cutNode) {
head = head.next;
}
head.next = null;
}
private ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode nextNode = head.next;
head.next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
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;
}
}
725. 分隔鏈表
給定一個頭結(jié)點為 root 的鏈表, 編寫一個函數(shù)以將鏈表分隔為 k 個連續(xù)的部分。
每部分的長度應(yīng)該盡可能的相等: 任意兩部分的長度差距不能超過 1，也就是說可能有些部分為 null。
這k個部分應(yīng)該按照在鏈表中出現(xiàn)的順序進行輸出，并且排在前面的部分的長度應(yīng)該大于或等于后面的長度。
返回一個符合上述規(guī)則的鏈表的列表。
舉例： 1->2->3->4, k = 5 // 5 結(jié)果 [ [1], [2], [3], [4], null ]
示例 1：
輸入:
root = [1, 2, 3], k = 5
輸出: [[1],[2],[3],[],[]]
解釋:
輸入輸出各部分都應(yīng)該是鏈表，而不是數(shù)組。
例如, 輸入的結(jié)點 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一個輸出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一個元素 output[4] 為 null, 它代表了最后一個部分為空鏈表。
示例 2：
輸入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
輸出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解釋:
輸入被分成了幾個連續(xù)的部分，并且每部分的長度相差不超過1.前面部分的長度大于等于后面部分的長度。
提示:
root 的長度范圍： [0, 1000].
輸入的每個節(jié)點的大小范圍：[0, 999].
k 的取值范圍： [1, 50].
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode cur = root;
int length = 0;
while(cur != null){
cur = cur.next;
length++;
}
int width = length / k;
// 前幾個子鏈表需要長度加一
int number = length % k;
cur = root;
ListNode[] ans = new ListNode[k];
for(int i = 0; i<k; i++){
ListNode head = cur;
for(int j = 0;j< width + (i < number ? 1 : 0) - 1; j++){
if(cur != null){
cur = cur.next;
}
}
if(cur != null){
ListNode prev = cur;
cur = cur.next;
prev.next = null;
}
ans[i] = head;
}
return ans;
}
}
328. 奇偶鏈表
給定一個單鏈表，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起。請注意，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性，而不是節(jié)點的值的奇偶性。
請嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點總數(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)當保持奇數(shù)節(jié)點和偶數(shù)節(jié)點的相對順序。
鏈表的第一個節(jié)點視為奇數(shù)節(jié)點，第二個節(jié)點視為偶數(shù)節(jié)點，以此類推。
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null){
return head;
}
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while(even != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
最后，期待您的訂閱和點贊，同時也期待您的批評與指正！一個堅持原創(chuàng)的博客，致力于用簡單的語言將編程這點事講清楚，如果你想入門編程，或者是對編程感興趣，請關(guān)注博主，每周都會更新
