devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode--链表_leetcode链表操作

作者：小小林熬夜学编程 | 2024-04-09 23:11:55

赞

踩

leetcode链表操作

LeetCode--链表

技巧

1.当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。使用虚拟头节点时，注意题目要求，返回时一般要head.next。跟双指针同时使用时，返回新链表的一定是head.next，而不是p.next!!!因为这个会动的指针最后已经不知道知道哪里去了，犯了一百遍的错误。
2.递归的思想相对迭代思想。不要跳进递归，而是利用明确的定义来实现算法逻辑。递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。
3.链表是一种兼具递归和迭代性质的数据结构，认真思考一下可以发现这个问题具有递归性质。
4.双指针。对于单链表来说，大部分技巧都属于快慢指针。

题目

1.合并两个有序链表
简单
在这里插入图片描述
思路：
输入两个有序链表，把他俩合并成一个新的有序链表。双指针分别指向两个链表，依次比较两个指针指向的值的大小，值比较小的连接到新链表上，同时将该指针往后移一位。循环往复，直到一个或两个链表遍历完毕。并将未遍历完的链表的剩余部分直接拼在新链表上。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    let ret = new ListNode(0,null);
    let p1= list1, p2 = list2, cur = ret;
    while(p1&&p2){
        if(p1.val<p2.val){
            cur.next = p1;
            p1 = p1.next;
        }
        else{
            cur.next = p2;
            p2 = p2.next;
        }
        cur = cur.next;
    }
    if(p1==null){
        cur.next = p2;
    }
    if(p2==null){
        cur.next = p1;
    }
    return ret.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

2.单链表的分解
中等
在这里插入图片描述
思路：
将这个链表一分为二，一个链表存小于x的值，一个链表存大于等于x的值，最后再把两个链表拼接。

注意：
1.由于直接在原链表上操作，将原链表指针消除，否则连得太乱循环会报错。
2.老问题 返回的时候注意返回的指针指向的是哪一个。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    let head1 = new ListNode(0,null),head2 = new ListNode(0,null);
    let p1 = head1, p2=head2, p = head;
    while(p){
        //小值放在p1 大值放在p2
        if(p.val<x){
            p1.next = p;
            p1 = p1.next;
        }
        else{
            p2.next = p;
            p2 = p2.next;
        }
        //由于直接在原链表上操作，将原链表指针消除，否则连得太乱循环会报错
        let temp = p.next;
        p.next = null;
        p = temp;
    }
    p1.next = head2.next;
    //添加虚拟头指针时返回时不要忘了next
    //这里第一次写成return p1.next，然而p1已经遍历到第一个链表最后了...
    return head1.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

3.合并k个有序链表
困难
在这里插入图片描述
思路：
1.两两归并排序。将k个链表以队列的形式弹出前两个归并，生成的新链表归并入数组末尾，继续弹出前两个排序，直到数组只有一个元素为止。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeTwoLists = function(listA,listB){
    let ret = new ListNode(0,null);
    let p1= listA, p2 = listB, cur = ret;
    while(p1&&p2){
        if(p1.val<p2.val){
            cur.next = p1;
            p1 = p1.next;
        }
        else{
            cur.next = p2;
            p2 = p2.next;
        }
        cur = cur.next;
    }
    if(p1==null){
        cur.next = p2;
    }
    if(p2==null){
        cur.next = p1;
    }
    return ret.next;
}
var mergeKLists = function(lists) {
    if(lists.length == 0)return null;
    while(lists.length > 1){
        lists.push(mergeTwoLists(lists.shift(),lists.shift()))
    }
    return lists[0]
};

  • 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

2.优先级队列（最小堆）
参考：合并k个有序链表、labuladong

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    // 两种思路：优先级队列（二叉堆） 和 JS-API排序
    // 首先实现一个优先级队列的数据结构（见下文 class: primaryQueue）

    // 声明一个优先级队列
    pq = new primaryQueue()
    // 构造一个新的链表头节点(第一个节点设置为0，避免空节点等情况)
    let result = new ListNode(0)
    let p = result

    // 插入所有list的头节点
    for(list of lists){
        if(list)
            pq.insert(list)
    }
    // 将目前队列中的节点进行比较、将最小的追加在原链表后
    while(pq.getSize()>1){
        const temp = pq.pop()
        p.next = temp
        p = p.next
        // temp 表示 本轮比较中最小的头节点
        // temp.next 表示这个链表中的下一个节点
        if(temp.next)
            pq.insert(temp.next)
    }

    return result.next  
};
// 实现优先级队列
class primaryQueue{
    // 定义一个“堆”，存放所有的元素
    constructor(){
        this.heap = []
        this.heap[0] = 0
    }
    // 交换任意两个节点
    swap(index1,index2){
        // 存一个别人的写法，有待研究
        // [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
        let temp = this.heap[index1]
        this.heap[index1] = this.heap[index2]
        this.heap[index2] = temp
    }
    // 返回父节点索引
    getParentIndex(node){
        return Math.floor(node/2)
    }
    // 返回左节点索引
    getLeftIndex(node){
        return node*2
    }
    // 返回右节点索引
    getRightIndex(node){
        return node*2 + 1
    }
    // 上浮
    shiftUp(node){
        // 在堆顶之前都while循环着
        while(node>1){
            let parentNode = this.getParentIndex(node)
            if(this.heap[parentNode].val > this.heap[node].val){
                this.swap(parentNode,node) // 交换值
                // 更新传入的node的索引(随着交换操作上移了)
                node = this.getParentIndex(node) 
            } else
                break //堆结构已经得到保证，不需要循环到堆顶了，直接跳出循环
        }
    }
    // 下沉
    shiftDown(node){
        // 在堆底之前都循环着
        while(this.heap[this.getLeftIndex(node)]){
            let tempIndex = this.getLeftIndex(node)
            let rightIndex = this.getRightIndex(node)
            if(this.heap[rightIndex] && this.heap[tempIndex].val > this.heap[rightIndex].val){
                tempIndex = rightIndex
            }
            if(this.heap[node].val<this.heap[tempIndex].val)
                break // 如果这个节点比两个子节点都大，退出循环
            this.swap(tempIndex,node)
            node = tempIndex
        }
    }
    // 插入节点
    insert(val){
        // 把节点放到堆底，执行上浮操作，让所有节点处于正确位置
        this.heap.push(val)
        this.shiftUp(this.heap.length-1)
    }
    // 删除最小的节点
    pop(){
        // 将原来最小的节点(堆顶)和堆底的节点交换
        const top = this.heap[1]
        this.swap(1,this.heap.length-1)
        this.heap.length-- // 删除交换后的堆底节点，即原来的堆顶节点
        this.shiftDown(1) // 对交换到堆定的节点进行下沉操作，保证堆的结构正确
        return top
    }
    // 返回最大的节点
    getMin(){
        return this.heap[1]
    }
    // 获取当前堆的大小
    getSize(){
        return this.heap.length
    }
}

  • 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
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118

4.删除单链表的倒数第 k 个节点
中等
在这里插入图片描述
思路：
双指针法。只用遍历一次链表即可。定义fast指针和slow指针，初始值为虚拟头结点。fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）。fast和slow同时移动，直到fast指向末尾。删除slow指向的下一个节点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let ret = new ListNode(0,head);
    let slow = fast = ret;
    while(n--)fast=fast.next;
    while(fast.next!=null){
        slow=slow.next;
        fast =fast.next;
    }
    slow.next =slow.next.next;
    return ret.next;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

5.单链表的中点
简单
在这里插入图片描述
**思路：**让两个指针 slow 和 fast 分别指向链表头结点 head。每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let fast = slow =head;
    while(fast&&fast.next){
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

6.环形链表II
中等
在这里插入图片描述
思路：
参考代码随想录环形链表II、labuladong
解决方案也是用快慢指针，每当慢指针 slow 前进一步，快指针 fast 就前进两步。如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。
假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步。fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了。所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。
在这里插入图片描述

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let slow = fast = head;
    if(!fast||!fast.next)return null;
    while(fast&&fast.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast){
            slow = head;
            while(slow!=fast){
                slow =slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return 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

7.两个链表是否相交
简单
在这里插入图片描述
思路：
交点不是数值相等，而是指针相等。
1.如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1。
在这里插入图片描述
2.curA指向链表A的头结点，curB指向链表B的头结点。求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到和curB 末尾对齐的位置, 此时就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。

//思路1
/**
 * 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 p1 = headA, p2 = headB;
    while(p1!=p2){
        p1=p1.next;
        p2=p2.next;
        if(p1==null&&p2==null)return null;
        if(p1==null){
            p1 = headB;
        }
        if(p2== null){
            p2 = headA;
        }
    }
    return p1;
};
//思路2
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getLen = function(head){
    let cur = head, len = 0;
    while(cur){
        len++;
        cur=cur.next; 
    }
    return len;
}
var getIntersectionNode = function(headA, headB) {
    let curA = headA, curB = headB;
    let lenA = getLen(headA), lenB = getLen(headB);
    if(lenA < lenB){
        //es6特性 交换
        [curA, curB] = [curB, curA];
        [lenA, lenB] = [lenB, lenA];
    } 
    let gap = lenA - lenB;
    while(gap--){
        curA=curA.next;
    }
    while(curA&&curA!=curB){
        curA = curA.next;
        curB = curB.next;
    }
    return curA;
};

  • 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
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69

8.反转链表
简单
在这里插入图片描述
思路：
1.首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
2.递归的简洁使用。参考labuladong

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    return reverse(null, head);
};
var reverse = function(pre,head){
    if(!head) return pre;
    let temp = head.next;
    head.next = pre;
    return reverse(head, temp);
}

//递归2
var reverseList = function(head) { 
    if (head == null || head.next == null) return head; // 递归终止条件
    let last = reverseList(head.next); // 递归反转后续节点
    head.next.next = head; // 将当前节点设置为后续节点的后续节点
    head.next = null; // 将当前节点的后续节点设置为空
    return last; // 返回反转后的链表
}

  • 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

9.反转链表前 N 个节点
在这里插入图片描述
思路：
base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。刚才直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 follower（第 n + 1 个节点），反转之后将 head 连接上。

let follower = null;
var reverseListTopN = function(head,n){
    if(n==1){
        follower = head.next;
        return head;
    }
    let last = reverseListTopN(head.next,n-1);
    head.next.next = head;
    head.next = follower;
    return last;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

10.反转链表一部分
中等
在这里插入图片描述
思路：
1.递归。如果 m == 1，就相当于反转链表开头的 n 个元素。当 m != 1，如果把 head 的索引视为 1，那么是想从第 m 个元素开始反转；如果把 head.next 的索引视为 1 ，那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的，反转区间为[m-1,n-1]。
2.迭代。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
 
let follower = null;
var reverseTopN = function(head,n){
    if(n==1){
        follower = head.next;
        return head;
    }
    let last = reverseTopN(head.next, n-1);
    head.next.next = head;
    head.next = follower;
    return last;
}
var reverseBetween = function(head, left, right) {
    if(left == 1){
        return reverseTopN(head, right);
    }
    head.next = reverseBetween(head.next, left-1, right-1);
    return head;
};

//迭代
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
 
var reverseBetween = function(head, left, right) {
    let ret = new ListNode(0,head);
    let pre = ret, cur = head;
    let prev= ret;
    for(let i = 1; i<left+1; i++){
        pre = pre.next;
        cur = cur.next;
        if(i==left-1)prev=pre;
    }
    // console.log(pre);
    // console.log(cur);
    // console.log(prev);
    let last = pre;
    let n = right-left;
    // console.log(last);
    while(n--){
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    prev.next = pre;
    // console.log(last);
    last.next = cur;
    // console.log(pre);
    // console.log(cur);
    return ret.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
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78

10. K 个一组翻转链表
困难
在这里插入图片描述
思路：
递归。先反转以 head 开头的 k 个元素。将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。将上述两个过程的结果连接起来。如果最后的元素不足 k 个，就保持不变。这就是 base case。「反转以 a 为头结点的链表」其实就是「反转 a 到 null 之间的结点」，「反转 a 到 b 之间的结点」只要更改函数签名，并把上面的代码中 null 改成 b 即可。注意 reverse 函数是反转区间 [a, b)。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    if(head==null)return null;
    var reverse = function(head,tail){
        let pre = null, cur = head;
        // while 终止的条件改为tail
        while(cur!=tail&&cur){
            let temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    let a = head, b = head;
    //左闭右开 区间 [a, b) 包含 k 个待反转元素
    for(let i = 0; i<k; i++){
        // 不足 k 个，不需要反转，base case
        if (b==null) return a;
        b=b.next;
    }
    let newHead = reverse(a,b);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b,k);
    return newHead;

};

  • 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

11.回文链表
简单
在这里插入图片描述
思路：
回文串就是正着读和反着读都一样的字符串。
1.原始链表反转存入一条新的链表，然后比较这两条链表是否相同。
2.利用二叉树后序遍历。
3.翻转后半部分链表，并进行回文串的判断。
定义slow，fast两个指针，slow每次走一步，fast每次走两步。当fast走到尾结点或者null时，slow到达中点。
在这里插入图片描述
如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步。
在这里插入图片描述
从slow开始反转后面的链表，现在就可以开始比较回文串了。
在这里插入图片描述
如果不想改变原有链表结构，只需：
在这里插入图片描述

p.next = reverse(q);

  • 1

第三种思路解法如下：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    if(!head&&head.next == null) return true;
    var reverse = function(head){
        let pre = null, cur = head, temp = null;
        while(cur){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    let slow = fast = head;
    while(fast&&fast.next){
        slow = slow.next;
        fast = fast.next.next;
    }
    let p = slow;
    //如果是奇数串 找到中点后slow还要往后走一步
    if(fast!=null){
        slow = slow.next;
    }
    let left = head;
    let q = reverse(slow);
    let right = q;
    while(right){
        if(left.val !== right.val){
            return false;
        }
        left = left.next;
        right = right.next;
    }
    //如果不想破坏原链表的结构 可加这一句
    p.next = reverse(q);
    return true;
};

  • 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

12.两两交换链表中的节点
中等
在这里插入图片描述
思路：
双指针。使用虚拟头节点处理。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let ret = new ListNode(0,head), temp=ret;
    while(temp.next&&temp.next.next){
        let pre = temp.next;
        let cur = temp.next.next;
        pre.next = cur.next;
        cur.next = pre;
        temp.next = cur;
        temp = pre;
    }
    return ret.next;
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

13.设计链表
中等
在这里插入图片描述

class LinkNode{
    constructor(val,next){
        this.val=val;
        this.next=next;
    }
}

var MyLinkedList = function() {
    this._size = 0;
    this._head = null;
    this._tail = null;
};

MyLinkedList.prototype.getNode = function(index){
    if(index<0 || index>=this._size) return null;
    if(index==0) return this._head;
    let cur = new LinkNode(0,this._head);
    for(let i = 0; i<=index;i++){
        cur = cur.next;
    }
    return cur;
}

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    if(!this.getNode(index)) return -1;
    let node = this.getNode(index);
    return node.val;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let node = new LinkNode(val,this._head);
    this._head = node;
    if(!this._tail){
        this._tail = node;
    }
    this._size++;
    return;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let node = new LinkNode(val,null);
    if(this._tail){
        this._tail.next = node;
        this._tail = node;
        this._size++;
        return;
    }
    this._tail = node;
    this._head = node;
    this._size++;
    return;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index>this._size) return;
    if(index<=0){
       this.addAtHead(val);
       return; 
    }
    if(index==this._size){
        this.addAtTail(val);
        return;
    }
    let node = new LinkNode(val, null);
    let last = this.getNode(index-1);
    node.next = last.next;
    last.next = node;
    this._size++;
    return;
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index>=this._size || index<0) return;
    if(index==0){
        this._head = this._head.next;
        if(this._size==1){
            this._tail=null;
        }
        this._size--;
        return;
    }
    let last = this.getNode(index-1)
    last.next = last.next.next;
    if(index==this._size-1){
        this._tail = last;
    }
    this._size--;
    return;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

  • 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
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120

14.移除链表元素
简单
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const ret = new ListNode(0,head);
    let cur = ret;
    while(cur.next){
        if(cur.next.val === val){
            cur.next = cur.next.next;
            continue;
        }
        cur = cur.next;
    }
    return ret.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
声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号