剑指offer（三）-链表

算法
字数统计: 3.2k字   |   阅读时长≈ 15分钟

一种线性结构表，数据元素在内存中分散存储，采用链式表示结构，即链表。

顺序表的存储结构是逻辑位置和物理位置都相邻，但链表是逻辑位置相邻，物理位置不一定相邻，且不能随机存取，但在插入和删除时，不需要移动元素。

链表存储结构由结点组成，每个结点包括一个数据域和一个指针域（指向下一个后继元素的地址）。除单链表外还有循环链表和双向链表，循环链表的最后一个结点的指针指向头结点，形成环。双向链表多了一个指向前驱元素的指针。

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

1
2
输入：head = [1,3,2]
输出：[2,3,1]

分析

按JavaScript数据结构，链表使用对象存储，数据结构为：

1
2
3
4
function ListNode(val) {
    this.val = val;
    this.next = null;
}

最后输出数组，故可以通过遍历将链表中的数据存入数组后再使用reverse()反转，或使用unshift()方法每次从数组头插入数据。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    if(!head )
        return [];
    let arr = [];
    //方法1
    while(head){
        arr.push(head.val);
        head = head.next;
    }
    return arr.reverse();
    //方法2
    while(head){
        arr.unshift(head.val);
        head = head.next;
    }
    return arr;
};

删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例:

1
2
3
4
5
6
7
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

分析

删除链表节点，即将要删除结点的前驱结点的next指针指向删除节点的next结点。需要注意的是要删除的结点是头结点和末尾结点的问题。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    if(!head)
        return [];
    //删除结点是头结点
    if(head.val === val){
        head = head.next;
        return head;
    }
       // return head;
    let current = head;
    let nextnode = current.next;
    while(current){
        if(nextnode.val === val && nextnode.next){//删除非尾结点
            current.next = nextnode.next;
            return head;
        }else if(nextnode.val === val && !nextnode.next){//删除尾结点
            current.next = null;
            return head;
        }
        current = nextnode;
        nextnode = nextnode.next;
    }
    return head;
};

链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

分析

使用快慢指针，快指针先走k步，慢指针再开始走，等快指针走到链表尾，慢指针即为倒数第k个结点。注意k大于链表长度的情况

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let fast = head;
    let slow = head;
    let path = 1;
    while(fast){
        if(path <= k){
            fast = fast.next;
            path ++;
        }else{
            fast = fast.next;
            slow = slow.next;
            path ++;
        }
    }
    if(path <= k){
        //k大于链表长度的情况
        slow = null;
    }
    return slow;
};

反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

分析

方法一：使用数组保存链表所有的值，再重新新建一个反转的链表

方法二：使用prev/current/nextnode指针。使current指针的next指向prev且current = nextnode向后遍历链表。使prev = current一直指向current的前一个，使反转链表成立。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    //方法一
    let arr = [];
    let result = null;
    if(!head){
        return result;
    }
    while(head){
        arr.unshift(head.val);
        head = head.next;
    }
    result = new ListNode(arr[0]);
    let p = result;
    for(let i = 0;i < arr.length - 1; i++){
        p.next = new ListNode(arr[i+1]);
        p = p.next;
    }
    return result;

    //方法二
    let prev = null;
    let current = head;
    let nextnode = null;
    if(!head){
        return prev;
    }
    while(current){
        nextnode = current.next;
        if(!prev){
            current.next = null;
        }else{
            current.next = prev;
        }
        prev = current;
        current = nextnode;
    }
    return prev;
};

两个链表的第一个公共结点

输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

分析

两种解释，公共节点即val值相同的两个节点，或两个链表的第一个交点

若为解释一，则可以通过保存链表1的值和所在位置，再遍历链表2找值相同且位置最前的节点，即为公共节点。

解释一和解释二都可以使用双指针解答。双指针公共遍历，若再某节点第一次相遇，则该节点为公共节点。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//解释一
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    let list = {};
    let path = 1;
    while(pHead1){
        list[pHead1.val] = path;
        pHead1 = pHead1.next;
        path ++;
    }
    let min = path;
    let result = null;
    while(pHead2){
        if(list[pHead2.val] && list[pHead2.val] <= min){
            result = pHead2;
            min = list[pHead2.val];
        }
        pHead2 = pHead2.next;
    }
    
    return result;
}

//通用解法
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let nodeA = headA;
    let nodeB = headB;
    while(nodeA!==nodeB){
        nodeA = nodeA ? nodeA.next : headB;
        nodeB = nodeB ? nodeB.next : headA;
    }
    return nodeA;
};

合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

分析

使用归并排序，通过两个链表的指针，依次将较小的值放入新链表中

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let list = new ListNode();
    let p = list;
    while(l1 && l2){
        if(l1.val<=l2.val){
            p.next = l1;
            l1 = l1.next;
            p = p.next;
        }else if(l2.val <= l1.val){
            p.next = l2;
            p = p.next;
            l2 = l2.next;
        }
    }
    while(l1){
        p.next = l1;
        l1 = l1.next;
        p = p.next;
    }
    while(l2){
        p.next = l2;
        l2 = l2.next;
        p = p.next;
    }
    return list.next;
};

删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

示例

1
2
3
4
5
输入：
{1,2,3,3,4,4,5}

返回值：
{1,2,5}

分析

使用prev指针指向当前节点的上一个节点，注意由空指针开始，next指向链表的头指针，防止无法删除从头指针开始重复的元素。在判断时，若出现重复元素，将prev指针的next指向下一个不重复的元素。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function deleteDuplication(pHead)
{
    let node = pHead;
    let p = null;
    let head = new ListNode(0);
    head.next = pHead;
    let prev = head;
    while(node && node.next){
        if(node.val === node.next.val){
            while(node.next && node.next.val === node.val){
                node = node.next;
            }
            prev.next = node.next;
            node = node.next;
        }else{
            prev= prev.next;
            node = node.next;
        }
    }
    return head.next;
    // write code here
}

链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

分析

使用数组保存每个节点，若某节点已经在数组中存在，则该节点为环的入口节点

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    let arr = [];
    if(!pHead){
        return null;
    }
    let node = pHead;
    while(node){
        if(arr.includes(node))
            return node;
        arr.push(node);
        node = node.next;
    }
    return null;
}
//快慢指针
//若存在环，则快慢指针会在环入口点相遇
var hasCycle = function(head) {
    if(!head)
        return null;
    let slow = head,fast = head.next;
    while(slow){
        if(!fast || !fast.next)
            return false;
        if(slow === fast)
            return slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    return null;
}

两个链表生成相加链表

  1. 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
  1. 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

1
2
3
4
5
输入：
[9,3,7],[6,3]

返回值：
{1,0,0,0}

分析

两个题目整体思路相同，即将两个链表的各个节点相加，并保存进位放入下个节点的相加中，将结果放入新链表中。若最后一位仍有进位，则新建一个节点保存进位放入新链表中。

题目1节点顺序为数字逆序，故每位相加的和放入新链表时即为数字相加和的顺序。

题目2节点顺序与数字顺序相同，故结果需要倒序插入每位的结果。且需要在相加前将链表的节点值存入栈中，保证栈顶的值为数字末尾的值。

解答

  1. 两个链表的顺序为数字逆序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let list = new ListNode();
    let p = list;
    let carry = 0;
    while(l1 || l2){
        let sum = (l1 ? l1.val : 0) + (l2? l2.val : 0) + carry;
        p.next = new ListNode(sum % 10);
        carry = Math.floor(sum/10);
        p = p.next;
        if(l1) l1 = l1.next;
        if(l2) l2 = l2.next;
    }
    if(carry){
        p.next = new ListNode(carry);
        p = p.next;
    }
    return list.next;
};
  1. 两个链表的顺序即数字的顺序 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
function addInList( head1 ,  head2 ) {
    let num1 = [],num2 = [];
    let p1 =head1,p2=head2;
    while(p1){
        num1.push(p1.val);
        p1 = p1.next;
    }
    while(p2){
        num2.push(p2.val);
        p2 =p2.next;
    }
    let p = null;
    let carry = 0;
    while(num1.length || num2.length){
        let sum = (num1.length ? num1.pop() : 0) + (num2.length ? num2.pop() : 0) + carry;
        carry = Math.floor(sum / 10);
        let node = new ListNode(sum % 10);
        node.next = p;
        p =node;
        //if(head1) head1 = head1.next;
        //if(head2) head2 = head2.next;
    }
    if(carry){
        let node = new ListNode(carry);
        node.next = p;
        p = node;
    }
    return p;
}
module.exports = {
    addInList : addInList
};
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2020-2024 Aweso Lynn
  • PV: UV: