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

排序链表

O(nlog(n))O(n* log(n)) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例1:

输入: 4->2->1->3
输出: 1->2->3->4

示例2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

分析:

题目看完就两个要求:

1. 时间复杂度: O(nlog(n))O(n* log(n))

2. 空间复杂度:O(1)O(1)

看到这里如果你脑海里没有各种排序的时空间复杂度表,就看下图。这道题的难点在于选择什么算法,先考虑时间复杂度,满足条件的只有堆排序、快排和归并排序。

此外,本题的对象是链表。当数列以链表的形式存储的时候,归并排序就不需要额外申请O(n)级别的空间。此时它的空间复杂度是O(1)O(1)。而快排和堆排序虽然都是速度很快的排序,但在链表中不是很合适。所以这道题优先选择归并排序来做。

方法一

思路

使用归并排序的方法实现。

详解

  1. 先判断是否只有一个元素,若只有一个元素,直接返回;

  2. 若不只有一个元素,首先找到链表的中间节点;

  3. 然后递归的对前半部分链表和后半部分链表分别进行递归排序;

  4. 最后对两个子链表进行归并操作。

const sortList = function (head) {
// 只有一个元素
if (head === null || head.next === null) {
return head;
}
// 快慢双指针
let slow = head; let fast = head;
while (slow.next && fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
const middle = slow.next;
slow.next = null;
// 一分为二
const left = head;
const right = middle;
return merge(sortList(left), sortList(right));
};
const merge = function (left, right) {
const tmp = new ListNode(null);
let p1 = left; let p2 = right; let p = tmp;
while (p1 && p2) {
if (p1.val < p2.val) {
const s = p1;
p1 = p1.next;
s.next = null;
p.next = s;
p = s;
} else {
const s = p2;
p2 = p2.next;
s.next = null;
p.next = s;
p = s;
}
}
if (p1) p.next = p1;
if (p2) p.next = p2;
return tmp.next;
};
function ListNode (val) {
this.val = val;
this.next = null;
}

复杂度分析

  • 时间复杂度:O(nlogn)O(n log n)

上述解法中,采用了归并排序的方法,归并排序时间复杂度 O(nlogn)O(n log n)

  • 空间复杂度:O(1)O(1)

上述解法中,申请了两个额外的临时存储空间,这将耗费 O(1)O(1) 的空间。

方法二

思路

借助数组实现,方法取巧。

详解

  1. 先判断是否只有一个元素,若只有一个元素,直接返回;

  2. 若不只有一个元素,首先把链表转为数组;

  3. 然后把数组排序后重建链表,方法取巧。

const sortList = function (head) {
// 只有一个元素
if (head === null || head.next === null) {
return head;
}
let cur = head; let index = 0; const arr = [];
// 链表转化为数组
while (cur !== null) {
arr[index] = cur.val;
cur = cur.next;
index += 1;
}
arr.sort((a, b) => a - b); // 数组升序排序
cur = head;
index = 0;
// 重建链表
while (cur !== null) {
cur.val = arr[index];
index += 1;
cur = cur.next;
}
return head;
};

复杂度分析

  • 时间复杂度: O(nlogn)O(n log n)

上述解法中,遍历两遍链表,时间复杂度 O(nlogn)O(n log n)

  • 空间复杂度: O(n)O(n)

上述解法中,申请了两个额外的数组空间,耗费的空间数量取决于链表的长度 nn ,空间复杂度 O(n)O(n)

相交链表

示例

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

在节点 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
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 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.

  • 在返回结果后,两个链表仍须保持原有的结构。

  • 可假定整个链表结构中没有循环。

  • 程序尽量满足 O(n)O(n) 时间复杂度,且仅用 O(1)O(1) 内存。

问题分析:

  • 两条链表相交,交点开始必定所有的节点值都相等。

  • 链表相交不仅仅是链表的值相同,而是链表的引用都相同,所以只要某个节点开始相等,就会一直相等。所以下图这种情况不存在。

方法一 暴力破解法

思路

如果给的数据结构是双向链表,很容易得到解法,两条链表从末尾开始遍历,直到链表同一个位置的两个值不相等即可。既然数据结构定了单向链表这种方法就不考虑了。

如果两条链表是一样的长度也很好得到解法,节点逐一比较,直到末尾节点值都是相等的就说明是相交点。我们可以按照此思路,先将两条链表处理成相同的长度在进行比较。

详解

  1. 计算链表长度

  2. 将较长的那条链表的长度调整为较短的那条的长度

  3. 继续遍历找出相交点

const getIntersectionNode = function (headA, headB) {
if (headA === null || headB === null) return null;
let pA = headA;
let pB = headB;
// 第一步:计算链表的长度
let lenA = 0;
let lenB = 0;
while (pA !== null) {
lenA += 1;
pA = pA.next;
}
while (pB !== null) {
lenB += 1;
pB = pB.next;
}
let lenDiff = lenA - lenB;
// 第二步:将较长的那条链表的长度调整为较短的那条的长度
// 若链表a比较长,需要调整a链表
pA = headA;
pB = headB;
if (lenDiff > 0) {
while (lenDiff !== 0) {
pA = pA.next;
lenDiff -= 1;
}
} else {
// 若链表b比较长,需要调整b链表
while (lenDiff !== 0) {
pB = pB.next;
lenDiff += 1;
}
}
// 第三步:继续遍历找出相交点
while (pA !== null) {
if (pA === pB) {
return pA;
}
pB = pB.next;
pA = pA.next;
}
return null;
};

复杂度分析

  • 时间复杂度:O(n)O(n),因为最差情况会完整遍历一遍链表,时间复杂度与链表长度呈线性正相关

  • 空间复杂度:O(1)O(1),因为只开辟了固定个数的变量空间,与输入值无关

方法二 双指针法

思路

通过加法的手段消除长度差。将两链表首尾相接形成 ab 和 ba 链表,此时我们构建了两条长度相同的链表,若 a 和 b 相交,则 ab 和 ba 也必定相交。

详解

  1. 定义两个指针 pA 和 pB;

  2. pA 从链表 a 的头部开始走,走完后再从链表 b 的头部开始走;

  3. pB 从链表 b 的头部开始走,走完后再从链表 a 的头部开始走;

  4. 如果存在相交结点,则两个指针必会相遇

const getIntersectionNode = function (headA, headB) {
if (headA === null || headB === null) return null;
let pA = headA;
let pB = headB;
while (pA !== pB) {
pA = pA === null ? headB : pA.next;
pB = pB === null ? headA : pB.next;
}
return pA;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    因为会完整遍历一遍链表,时间复杂度与链表长度呈线性关系

  • 空间复杂度:O(1)O(1)

    因为只开辟了固定个数的变量空间,与输入值无关

奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)O(1),时间复杂度应为 O(nodes)O(nodes),nodes 为节点总数。

  • 应当保持奇数节点和偶数节点的相对顺序。

  • 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

示例

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL

方法一 奇偶链表分离法

思路

将链表中所有元素按照奇数位置、偶数位置划分为两个链表:odd 链表、event 链表,遍历结束,直接将偶数链表挂在奇数链表之后。

详解

  1. 如果链表中节点个数为 0、1、2 个时,链表自身已满足奇偶链表,直接返回 head 节点即可;

  2. 定义 odd 变量指向头节点、even 和 evenHeadPointer 变量指向链表的第二个节点,其中 head 即代表奇数链表的头节点、evenHeadPointer 即代表偶数链表的头节点;

  3. while 循环遍历链表(利用 odd、even 变量遍历),利用原链表中奇数位置节点的子节点应该挂到偶链表中、偶数位置节点的子节点应该挂到奇链表中交叉遍历赋值,odd、even 变量永远指向奇链表、偶链表最后一个节点;

  4. 奇链表最后一个节点 odd 的子节点指向偶链表的头节点 evenHeadPointer;

  5. 返回 head 头节点即可;

/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
const oddEvenList = function (head) {
if (head === null || head.next === null || head.next.next === null) {
return head;
}
let odd = head;
let even = head.next;
const evenHeadPointer = head.next;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHeadPointer;
return head;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    while 循环遍历一次链表,以第一个节点作为奇数链表的头节点,第二个节点作为偶数链表的头节点,交叉串联起奇数、偶数链表,时间复杂度为 O(n)O(n)

  • 空间复杂度:O(1)O(1) 新增三个变量用于存储链表头节点,空间复杂度:O(1)O(1)

方法二 数组暂存法

思路

遍历链表并利用数组暂存链表节点,然后在数组中对奇数、偶数位置的节点进行串联;

详解

  1. 如果链表中节点个数为 0、1、2 个时,链表自身已满足奇偶链表,直接返回 head 节点即可;

  2. 定义一个数组暂存链表节点;

  3. while 循环遍历链表(利用 head 变量遍历),将每一个节点 push 到数组中,并且从第三个节点开始,将第三个节点作为子节点挂到第一个节点上,第四个节点作为子节点挂到第二个节点上,以此类推;

  4. 遍历到最后一个节点时,倒数第二个节点的子节点赋值为 null;

  5. 如果数组长度为偶数个,则数组的倒数第二个元素是奇链表的最后一个节点,如果数组长度为奇数个,则数组的最后一个元素是奇链表的最后一个节点;

  6. 数组的第二个元素是偶链表的头节点;

  7. 串联奇偶链表,直接将奇链表的最后一个节点的 next 指向偶链表的头节点;

  8. 返回数组的第一个元素即可;

/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
const oddEvenList = function (head) {
// 如果链表中元素个数少于2个,直接返回链表
if (head === null || head.next === null || head.next.next === null) {
return head;
}
// 为了防止链表节点丢失,利用一个数组暂存链表
const linkArr = [];
while (head != null) {
linkArr.push(head);
const len = linkArr.length;
// 从第三个节点开始处理next
if (len > 2) {
linkArr[len - 3].next = linkArr[len - 1];
}
head = head.next;
if (head === null) {
linkArr[len - 2].next = null;
}
const isOdd = len % 2 !== 0;
if (!isOdd) {
linkArr[len - 2].next = linkArr[1];
} else {
linkArr[len - 1].next = linkArr[1];
}
}
return linkArr[0];
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    while 循环遍历一次链表,从第三个节点开始处理 next,时间复杂度:O(n)O(n)

  • 空间复杂度:O(n)O(n)

    借用一个跟链表等长的数组暂存链表元素,空间复杂度为O(n)O(n)