前端程序员学好算法系列（四）链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了前端程序员学好算法系列（四）链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2725字，纯文字阅读大概需要4分钟。

内容图文

24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

解题：我们定义4个指针如上进行节点交换，
1.给head添加一个虚拟头节点thead
2.定义4个指针 p， node1， node2， next 我们需要将p.next ->node2  node1.next -> next    node2.next ->node1        完成以后将 p指针移动到node1
3.我们需要判断 p.next 和p.next.next 都不为空，这样next 最差为null 不会越界

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    let thead = new ListNode(0);
    thead.next = head;
    let p = thead;
    while(p.next != null && p.next.next != null){
        let node1 = p.next;
        let node2 = node1.next;
        let next = node2.next

        p.next = node2;
        node1.next = next;
        node2.next = node1;
        p = node1;
    }
    return thead.next;
};

237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

 

示例 1:

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

解题：

1.我们无法直接删除给定的节点，我们只能拿到给定节点的下一个节点的值，

2.我们用该节点的下一个节点的值覆盖当前节点的值，然后删除下一个节点，即相当于实现了对该节点的删除

3.我们处理node 为null和node.next为null的特殊情况

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
     if(node == null){
        return
     }
     if(node.next == null){
          delete node
          node = null
          return
     }
     node.val = node.next.val
     node.next = node.next.next
};

19. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

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

当删除了倒数第二个节点后，链表变为 1->2->3->5.

解题：
1.给head设置虚拟头节点
2.设置fast 和show两个指针
3.fast指针先移动n位，然后fast指针和show指针同时移动
4.当fast指针为空时，show.next节点即为需要删除的节点，我们把show.next ->show.next.next

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let preHead = new ListNode(0)
    preHead.next = head
    let fast = preHead, slow = preHead
    // 快先走 n+1 步
    while(n--) {
        fast = fast.next
    }
    let i = 0
    // fast、slow 一起前进
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next
        
    }
    slow.next = slow.next.next
    return preHead.next
};

链表的js算法就先介绍到这里了

 

内容总结

以上是互联网集市为您收集整理的前端程序员学好算法系列（四）链表全部内容，希望文章能够帮你解决前端程序员学好算法系列（四）链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---