排序链表、相交链表和奇偶链表

排序链表

O(nlog(n))O(n* log(n))
时间复杂度和常数级空间复杂度下,对链表进行排序。
示例1:
1
输入: 4->2->1->3
2
输出: 1->2->3->4
Copied!
示例2:
1
输入: -1->5->3->4->0
2
输出: -1->0->3->4->5
Copied!

分析:

题目看完就两个要求:
1. 时间复杂度:
O(nlog(n))O(n* log(n))
2. 空间复杂度:
O(1)O(1)
看到这里如果你脑海里没有各种排序的时空间复杂度表,就看下图。这道题的难点在于选择什么算法,先考虑时间复杂度,满足条件的只有堆排序、快排和归并排序。
此外,本题的对象是链表。当数列以链表的形式存储的时候,归并排序就不需要额外申请O(n)级别的空间。此时它的空间复杂度是
O(1)O(1)
。而快排和堆排序虽然都是速度很快的排序,但在链表中不是很合适。所以这道题优先选择归并排序来做。

方法一

思路
使用归并排序的方法实现。
详解
  1. 1.
    先判断是否只有一个元素,若只有一个元素,直接返回;
  2. 2.
    若不只有一个元素,首先找到链表的中间节点;
  3. 3.
    然后递归的对前半部分链表和后半部分链表分别进行递归排序;
  4. 4.
    最后对两个子链表进行归并操作。
1
const sortList = function (head) {
2
// 只有一个元素
3
if (head === null || head.next === null) {
4
return head;
5
}
6
// 快慢双指针
7
let slow = head; let fast = head;
8
while (slow.next && fast.next && fast.next.next) {
9
slow = slow.next;
10
fast = fast.next.next;
11
}
12
const middle = slow.next;
13
slow.next = null;
14
// 一分为二
15
const left = head;
16
const right = middle;
17
return merge(sortList(left), sortList(right));
18
};
19
const merge = function (left, right) {
20
const tmp = new ListNode(null);
21
let p1 = left; let p2 = right; let p = tmp;
22
while (p1 && p2) {
23
if (p1.val < p2.val) {
24
const s = p1;
25
p1 = p1.next;
26
s.next = null;
27
p.next = s;
28
p = s;
29
} else {
30
const s = p2;
31
p2 = p2.next;
32
s.next = null;
33
p.next = s;
34
p = s;
35
}
36
}
37
if (p1) p.next = p1;
38
if (p2) p.next = p2;
39
return tmp.next;
40
};
41
function ListNode (val) {
42
this.val = val;
43
this.next = null;
44
}
Copied!
复杂度分析
  • 时间复杂度:
    O(nlogn)O(n log n)
上述解法中,采用了归并排序的方法,归并排序时间复杂度
O(nlogn)O(n log n)
  • 空间复杂度:
    O(1)O(1)
上述解法中,申请了两个额外的临时存储空间,这将耗费
O(1)O(1)
的空间。

方法二

思路
借助数组实现,方法取巧。
详解
  1. 1.
    先判断是否只有一个元素,若只有一个元素,直接返回;
  2. 2.
    若不只有一个元素,首先把链表转为数组;
  3. 3.
    然后把数组排序后重建链表,方法取巧。
1
const sortList = function (head) {
2
// 只有一个元素
3
if (head === null || head.next === null) {
4
return head;
5
}
6
let cur = head; let index = 0; const arr = [];
7
// 链表转化为数组
8
while (cur !== null) {
9
arr[index] = cur.val;
10
cur = cur.next;
11
index += 1;
12
}
13
arr.sort((a, b) => a - b); // 数组升序排序
14
cur = head;
15
index = 0;
16
// 重建链表
17
while (cur !== null) {
18
cur.val = arr[index];
19
index += 1;
20
cur = cur.next;
21
}
22
return head;
23
};
Copied!
复杂度分析
  • 时间复杂度:
    O(nlogn)O(n log n)
上述解法中,遍历两遍链表,时间复杂度
O(nlogn)O(n log n)
  • 空间复杂度:
    O(n)O(n)
上述解法中,申请了两个额外的数组空间,耗费的空间数量取决于链表的长度
nn
,空间复杂度
O(n)O(n)

相交链表

示例
编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
在节点 c1 开始相交。
示例 1:
1
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
2
输出:Reference of the node with value = 8
3
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
Copied!
示例 2:
1
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
2
输出:Reference of the node with value = 2
3
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
Copied!
示例 3:
1
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
2
输出:null
3
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
4
解释:这两个链表不相交,因此返回 null。
Copied!
注意:
  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足
    O(n)O(n)
    时间复杂度,且仅用
    O(1)O(1)
    内存。
问题分析:
  • 两条链表相交,交点开始必定所有的节点值都相等。
  • 链表相交不仅仅是链表的值相同,而是链表的引用都相同,所以只要某个节点开始相等,就会一直相等。所以下图这种情况不存在。

方法一 暴力破解法

思路
如果给的数据结构是双向链表,很容易得到解法,两条链表从末尾开始遍历,直到链表同一个位置的两个值不相等即可。既然数据结构定了单向链表这种方法就不考虑了。
如果两条链表是一样的长度也很好得到解法,节点逐一比较,直到末尾节点值都是相等的就说明是相交点。我们可以按照此思路,先将两条链表处理成相同的长度在进行比较。
详解
  1. 1.
    计算链表长度
  2. 2.
    将较长的那条链表的长度调整为较短的那条的长度
  3. 3.
    继续遍历找出相交点
1
const getIntersectionNode = function (headA, headB) {
2
if (headA === null || headB === null) return null;
3
4
let pA = headA;
5
let pB = headB;
6
7
// 第一步:计算链表的长度
8
let lenA = 0;
9
let lenB = 0;
10
while (pA !== null) {
11
lenA += 1;
12
pA = pA.next;
13
}
14
while (pB !== null) {
15
lenB += 1;
16
pB = pB.next;
17
}
18
let lenDiff = lenA - lenB;
19
20
// 第二步:将较长的那条链表的长度调整为较短的那条的长度
21
// 若链表a比较长,需要调整a链表
22
pA = headA;
23
pB = headB;
24
if (lenDiff > 0) {
25
while (lenDiff !== 0) {
26
pA = pA.next;
27
lenDiff -= 1;
28
}
29
} else {
30
// 若链表b比较长,需要调整b链表
31
while (lenDiff !== 0) {
32
pB = pB.next;
33
lenDiff += 1;
34
}
35
}
36
37
// 第三步:继续遍历找出相交点
38
while (pA !== null) {
39
if (pA === pB) {
40
return pA;
41
}
42
pB = pB.next;
43
pA = pA.next;
44
}
45
return null;
46
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
    ,因为最差情况会完整遍历一遍链表,时间复杂度与链表长度呈线性正相关
  • 空间复杂度:
    O(1)O(1)
    ,因为只开辟了固定个数的变量空间,与输入值无关

方法二 双指针法

思路
通过加法的手段消除长度差。将两链表首尾相接形成 ab 和 ba 链表,此时我们构建了两条长度相同的链表,若 a 和 b 相交,则 ab 和 ba 也必定相交。
详解
  1. 1.
    定义两个指针 pA 和 pB;
  2. 2.
    pA 从链表 a 的头部开始走,走完后再从链表 b 的头部开始走;
  3. 3.
    pB 从链表 b 的头部开始走,走完后再从链表 a 的头部开始走;
  4. 4.
    如果存在相交结点,则两个指针必会相遇
1
const getIntersectionNode = function (headA, headB) {
2
if (headA === null || headB === null) return null;
3
4
let pA = headA;
5
let pB = headB;
6
while (pA !== pB) {
7
pA = pA === null ? headB : pA.next;
8
pB = pB === null ? headA : pB.next;
9
}
10
return pA;
11
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
    因为会完整遍历一遍链表,时间复杂度与链表长度呈线性关系
  • 空间复杂度:
    O(1)O(1)
    因为只开辟了固定个数的变量空间,与输入值无关

奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为
O(1)O(1)
,时间复杂度应为
O(nodes)O(nodes)
,nodes 为节点总数。
  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
示例
1
输入: 1->2->3->4->5->NULL
2
输出: 1->3->5->2->4->NULL
Copied!
1
输入: 2->1->3->5->6->4->7->NULL
2
输出: 2->3->6->7->1->5->4->NULL
Copied!

方法一 奇偶链表分离法

思路
将链表中所有元素按照奇数位置、偶数位置划分为两个链表:odd 链表、event 链表,遍历结束,直接将偶数链表挂在奇数链表之后。
详解
  1. 1.
    如果链表中节点个数为 0、1、2 个时,链表自身已满足奇偶链表,直接返回 head 节点即可;
  2. 2.
    定义 odd 变量指向头节点、even 和 evenHeadPointer 变量指向链表的第二个节点,其中 head 即代表奇数链表的头节点、evenHeadPointer 即代表偶数链表的头节点;
  3. 3.
    while 循环遍历链表(利用 odd、even 变量遍历),利用原链表中奇数位置节点的子节点应该挂到偶链表中、偶数位置节点的子节点应该挂到奇链表中交叉遍历赋值,odd、even 变量永远指向奇链表、偶链表最后一个节点;
  4. 4.
    奇链表最后一个节点 odd 的子节点指向偶链表的头节点 evenHeadPointer;
  5. 5.
    返回 head 头节点即可;
1
/**
2
* Definition for singly-linked list.
3
* function ListNode(val) {
4
* this.val = val;
5
* this.next = null;
6
* }
7
*/
8
/**
9
* @param {ListNode} head
10
* @return {ListNode}
11
*/
12
const oddEvenList = function (head) {
13
if (head === null || head.next === null || head.next.next === null) {
14
return head;
15
}
16
let odd = head;
17
let even = head.next;
18
const evenHeadPointer = head.next;
19
while (even != null && even.next != null) {
20
odd.next = even.next;
21
odd = odd.next;
22
even.next = odd.next;
23
even = even.next;
24
}
25
odd.next = evenHeadPointer;
26
return head;
27
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
    while 循环遍历一次链表,以第一个节点作为奇数链表的头节点,第二个节点作为偶数链表的头节点,交叉串联起奇数、偶数链表,时间复杂度为
    O(n)O(n)
  • 空间复杂度:
    O(1)O(1)
    新增三个变量用于存储链表头节点,空间复杂度:
    O(1)O(1)

方法二 数组暂存法

思路
遍历链表并利用数组暂存链表节点,然后在数组中对奇数、偶数位置的节点进行串联;
详解
  1. 1.
    如果链表中节点个数为 0、1、2 个时,链表自身已满足奇偶链表,直接返回 head 节点即可;
  2. 2.
    定义一个数组暂存链表节点;
  3. 3.
    while 循环遍历链表(利用 head 变量遍历),将每一个节点 push 到数组中,并且从第三个节点开始,将第三个节点作为子节点挂到第一个节点上,第四个节点作为子节点挂到第二个节点上,以此类推;
  4. 4.
    遍历到最后一个节点时,倒数第二个节点的子节点赋值为 null;
  5. 5.
    如果数组长度为偶数个,则数组的倒数第二个元素是奇链表的最后一个节点,如果数组长度为奇数个,则数组的最后一个元素是奇链表的最后一个节点;
  6. 6.
    数组的第二个元素是偶链表的头节点;
  7. 7.
    串联奇偶链表,直接将奇链表的最后一个节点的 next 指向偶链表的头节点;
  8. 8.
    返回数组的第一个元素即可;
1
/**
2
* Definition for singly-linked list.
3
* function ListNode(val) {
4
* this.val = val;
5
* this.next = null;
6
* }
7
*/
8
/**
9
* @param {ListNode} head
10
* @return {ListNode}
11
*/
12
const oddEvenList = function (head) {
13
// 如果链表中元素个数少于2个,直接返回链表
14
if (head === null || head.next === null || head.next.next === null) {
15
return head;
16
}
17
// 为了防止链表节点丢失,利用一个数组暂存链表
18
const linkArr = [];
19
while (head != null) {
20
linkArr.push(head);
21
const len = linkArr.length;
22
// 从第三个节点开始处理next
23
if (len > 2) {
24
linkArr[len - 3].next = linkArr[len - 1];
25
}
26
head = head.next;
27
if (head === null) {
28
linkArr[len - 2].next = null;
29
}
30
const isOdd = len % 2 !== 0;
31
if (!isOdd) {
32
linkArr[len - 2].next = linkArr[1];
33
} else {
34
linkArr[len - 1].next = linkArr[1];
35
}
36
}
37
return linkArr[0];
38
};
Copied!
复杂度分析
  • 时间复杂度:
    O(n)O(n)
    while 循环遍历一次链表,从第三个节点开始处理 next,时间复杂度:
    O(n)O(n)
  • 空间复杂度:
    O(n)O(n)
    借用一个跟链表等长的数组暂存链表元素,空间复杂度为
    O(n)O(n)
最近更新 1yr ago