链表算法的解题思路

miao8862 · 简书 · · 2021-04-04 02:25

一般追赶问题，环大小，都可以使用链表的双指针问题解决。

判断一个链表是否有环？

创建两个指针，一个快指针，一个慢指针，快指针每次移动两步，慢指针每次移到一步，当它们能在某个节点相遇，代表着这个链表有环；当快指针走完链表时，还没有相遇的节点，就代表着这是个无环的链表

// 链表节点
function LinkNode(val) {
  this.val = val;
  this.next = null;
}

// 判断单向链表是否有环
function hasLoop(link) {
  let fast = link
  let slow = link
  while(fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
    if(fast &&　fast.val === slow.val) {
      return true;
    }
  }
  return false;
}

const node1 = new LinkNode(1)
const node2= new LinkNode(2)
const node3 = new LinkNode(3)
const node4 = new LinkNode(4)
const node5 = new LinkNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

let isLoop = hasLoop(node1)
console.log(isLoop); // false;

node5.next = node2
isLoop = hasLoop(node1)
console.log(isLoop); // true;

判断环的长度

在判断有环的基础上，在第一次环的相交点，继续让快指针和慢指针往下走，当他们再次相交时，慢指针所走的步骤就是环的长度。因为快指针的步长是2，慢指针的步长是1，当它们再次相交时，快指针刚好比慢指针多走一圈，这时慢指针走的次数，就是这个环的长度。

function getCycleLength(link) {
  let fast = link
  let slow = link
  let len = 0;
  let isCycle = false;
  while(fast && fast.next) {
    fast = fast.next.next
    slow = slow.next
    if(isCycle) {
      len++;
    }
    if(fast &&　fast.val === slow.val) {
      if(!isCycle) { 
        isCycle = true; 
      }else {
        return len;
      }
    }
  }
  return 0;
}

const node1 = new LinkNode(1)
const node2= new LinkNode(2)
const node3 = new LinkNode(3)
const node4 = new LinkNode(4)
const node5 = new LinkNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node2

console.log(getCycleLength(node1)); // 4

判断入环点

链表头结点到入环点的距离 = 快慢指针首次相交点到入环点的距离
假设头结点到入环点的距离为D，入环点到首次相交点的距离为D1，首次相交点到入环点的距离为D2：

当首次相交时，慢指针走的距离是：D + D1，快指针走的距离是：D + D1 + D2 + D1 = D + D2 + 2D1
因为快指针走的步长为2，是慢指针的2倍，所以 2(D + D1) = D + D2 + 2D1，推导出D = D2

解题思路：

第一步，还是用快慢指针解决：让快指针走2步，让慢指针走1步，找到它们第一次的相交点
相交时，让慢指针指向头节点，让快指针停留在相交点，并改为快指针的的步长为1，当快慢指针再次相交时，就是这个环的入环点

// 获取单链表环的入环节点
function getCycleEntry(link) {
  let fast = link
  let slow = link
  let isCycle = false;
  while(fast && fast.next) {
    // 如果还未相交过，则快指针步长为2
    if(!isCycle) {
      fast = fast.next.next
      // 如果相交过一次，则快指针步长改为1
    }else {
      fast = fast.next
    }
    slow = slow.next

    if(fast &&　fast.val === slow.val) {
      // 如果是首次相遇，将有环标识设为true，并将慢指针指向头节点
      if(!isCycle) { 
        isCycle = true;
        slow = link;
        // 如果为第二次相交，则为入环点
      }else {
        return fast;
      }
    }
  }
  return null;
}


const node1 = new LinkNode(1)
const node2= new LinkNode(2)
const node3 = new LinkNode(3)
const node4 = new LinkNode(4)
const node5 = new LinkNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node2

console.log(getCycleEntry(node1));  // LinkNode {2, next: node5 }

求一个单链表倒数第k个节点到最后一个节点的链表

比如 1=>2=>3=>4=>5,求倒数第2个到最后一个节点的链表：4=>5, k < 链表长度。
解题思路：使用两个指针，一个指针从第一个节点开始，第二个指针第k个节点开始，当第二个指针走到终点时，第一个指针所指的节点开始，就是所求的链表

function getLastLink(link, k) {
  let p1 = link
  let p2 = link
  for(let i = 0; i < k; i++) {
    if(p2) {
      p2 = p2.next
    }
  }
  while(p2) {
    p2 = p2.next
    p1 = p1.next
  }
  return p1
}
const node1 = new LinkNode(1)
const node2= new LinkNode(2)
const node3 = new LinkNode(3)
const node4 = new LinkNode(4)
const node5 = new LinkNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

console.log(getLastLink(node1, 2));  // LinkNode { val: 4, next: LinkNode { val: 5, next: null } }

原文地址：访问原文地址
快照地址：访问文章快照

分享到微博