leetcode 链表相关题目解析

摘要：同时保有当前链表的尾部的指针以及头部的节点指针。链表可能只有部分成环这意味着。头部的引用尾部的引用始终指向尾部忽略虚假的头部链表相加原题地址。生成虚假的头部后两个链表两两相加注意进位以及保留位即可。链表是没有发生改变的。

本文基于leetcode的探索链表卡片所编写。遗憾的是, 我的卡片的进度为80%, 依然没有全部完成。我在探索卡片的时候, 免不了谷歌搜索。并且有一些题目, 我的解答可能不是最优解。敬请见谅。

链表属于比较简单的数据结构, 在这里我在过多的赘述。值的注意的是, 本文都是基于单链表的, 双链表的设计我还没有实现。

关于链表的算法题目, 我自己总结了以下几种套路, 或者说常见的手段

同时保有当前节点的指针, 以及当前节点的前一个节点的指针。

快慢指针, fast指针的移动速度是slow指针的两倍, 如果链表成环那么fast和slow必然会相遇。

虚假的链表头, 通过 new ListNode(0), 创建一个虚假的头部。获取真正链表只需返回head.next(这在需要生成一个新链表的时候很有用)。

同时保有当前链表的尾部的指针, 以及头部的节点指针。

善用while循环。

链表的头部和尾部是链表比较特殊的节点, 需要注意区别对待

原题的地址, 我在原题的基础使用了TypeScript模拟实现了链表。

链表需要拥有以下几种方法:

get, 根据链表的索引获取链表节点的value

addAtTail, 添加一个节点到链表的尾部

addAtHead, 添加一个节点到链表的头部

addAtIndex, 添加一个节点到链表的任意位置

deleteAtIndex, 删除任意位置的节点

// 定义链表节点类以及链表类的接口
interface LinkedListNodeInterface {
  val: number;
  next: LinkedListNode;
}

interface LinkedListInterface {
  head: LinkedListNode;
  length: number;
  get(index: number): number;
  addAtHead(val: number): void;
  addAtTail(val: number): void;
  addAtIndex(index: number, val: number): void;
  deleteAtIndex(index: number): void
}

class LinkedListNode implements LinkedListNodeInterface {
  constructor (
    public val: number = null,
    public next: LinkedListNode = null
  ) {}
}

class LinkedList implements LinkedListInterface {
  constructor (
    public head: LinkedListNode = null,
    public length: number = 0
  ) {}

  /**
   * 通过while循环链表, 同时在循环的过程中使用计数器计数, 既可以实现
   */
  public get(index: number): number {
    if (index >= 0 && index < this.length) {
      let num: number = 0
      let currentNode: LinkedListNode = this.head
      while (index !== num) {
        num += 1
        currentNode = currentNode.next
      }
      return currentNode.val
    }
    return -1
  }

  /**
   * 将新节点的next属性指向当前的head, 将head指针指向新节点
   */
  public addAtHead (val: number): void {
    let newNode: LinkedListNode = new LinkedListNode(val, this.head)
    this.head = newNode
    this.length += 1
  }

  /**
   * 将链表尾部的节点的next属性指向新生成的节点, 获取链表尾部的节点需要遍历链表
   */
  public addAtTail(val: number): void {
    let newNode: LinkedListNode = new LinkedListNode(val, null)
    let currentNode: LinkedListNode = this.head
    if (!this.head) {
      this.head = newNode
    } else {
      while (currentNode && currentNode.next) {
        currentNode = currentNode.next
      }
      currentNode.next = newNode
    }
    this.length += 1
  }

  /**
   * 这里需要需要运用技巧, 遍历链表的同时, 同时保留当前的节点和当前节点的前一个节点的指针
   */
  public addAtIndex(index: number, val: number): void {
    if (index >= 0 && index <= this.length) {
      let newNode: LinkedListNode = null
      if (index === 0) {
        // 如果index为0, 插入头部需要与其他位置区别对待
        this.addAtHead(val)
      } else {
        let pointer: number = 1
        let prevNode: LinkedListNode = this.head
        let currentNode: LinkedListNode = this.head.next
        while (pointer !== index && currentNode) {
          prevNode = currentNode
          currentNode = currentNode.next
          pointer += 1
        }
        // 中间插入
        newNode = new LinkedListNode(val, currentNode)
        prevNode.next = newNode
        this.length += 1
      }
    }
  }

  public deleteAtIndex(index: number): void {
    if (index >= 0 && index < this.length && this.length > 0) {
      if (index === 0) {
        this.head = this.head.next
      } else {
        let pointer: number = 1
        let prevNode: LinkedListNode = this.head
        let currentNode: LinkedListNode = this.head.next
        // 值得注意的是这里的判断条件使用的是currentNode.next
        // 这意味着currentNode最远到达当前链表的尾部的节点，而非null
        // 这是因为prevNode.next = prevNode.next.next, 我们不能取null的next属性
        while (pointer !== index && currentNode.next) {
          prevNode = currentNode
          currentNode = currentNode.next
          pointer += 1
        }
        prevNode.next = prevNode.next.next
      }
      this.length -= 1
    }
  }
}

原题地址, 将环形链表想象成一个跑道, 运动员的速度是肥宅的两倍, 那么经过一段时间后, 运动员必然会超过肥宅一圈。这个时候, 运动员和肥宅必然会相遇。快慢指针的思想就是源于此。

/**
 * 判断链表是否成环
 */
function hasCycle (head: LinkedListNode): boolean {
  // 快指针
  let flst = head
  // 慢指针
  let slow = head

  while (flst && flst.next && flst.next.next) {
    flst = flst.next.next
    slow = flst.next
    if (flst === slow) {
      return true
    }
  }
  return false
}

原题地址, 在环形链表的基础上, 我们需要获取环形链表的入口。同样使用快慢指针实现。但是值的注意的是。链表可能只有部分成环, 这意味着。快慢指针相遇的点, 可能并不是环的入口。

慢节点的运动距离为, a + b - c

快节点的运动距离为, 2b + a - c

快节点的运动距离是慢节点的两倍。可以得出这个公式 2(a + b - c) = 2b + a - c, 化简 2a - 2c = a - c, 可以得出 a = c。

相遇的点距离入口的距离, 等于起点距离入口距离

function hasCycleEntrance (head: LinkedListNode): LinkedListNode | Boolean {
  // 快指针
  let flst = head
  // 慢指针
  let slow = head
  while (flst && flst.next && flst.next.next) {
    flst = flst.next.next
    slow = flst.next
    // 快指针移动到入口，并且速度变为1
    if (flst === slow) {
      // 变道起点
      flst = head
      // a 和 c距离是一致的
      // 每一次移动一个next，必然会在入口出相遇
      while (flst !== slow) {
        flst = flst.next
        slow = slow.next
      }
      return flst
    }
  }
  return false
}

原题地址, 相交链表的解题思路依然是使用快慢指针。思路见下图, 将a链的tail链接到b链head, 如果a与b链相交, 那么就会成环。套用上一题的思路就可以获取到a与b的交点。

function hasCross (headA: LinkedListNode, headB: LinkedListNode): LinkedListNode {
  if (headA && headB) {
        
    // 自身相等的情况下
    if (headA === headB) {
        return headA
    }
    
    // a链的tail连上b链的head
    let lastA: LinkedListNode = headA
    let lastB: LinkedListNode = headB
    
    while (lastA && lastA.next) {
        lastA = lastA.next
    }
    
    lastA.next = headB
    
    let fast: LinkedListNode = headA
    let slow: LinkedListNode = headA
    
    while (fast && fast.next && fast.next.next) {
        slow = slow.next
        fast = fast.next.next
        
        if (slow === fast) {
            fast = headA
            
            while (slow !== fast) {
                slow = slow.next
                fast = fast.next
                
                if (slow === fast) {
                    lastA.next = null
                    return slow
                }
            }
            lastA.next = null
            return fast
        } 
    }
    lastA.next = null  
    return null  
  } 
}

原题地址, 这里我使用的是比较笨的办法, 先计算链表的长度, 获取正序的时n的大小。然后按照删除链表中某一个节点的方法进行删除即可。需要区分删除的是否是第一个。

原题地址, 常见的反转链表的方式就是使用递归或者迭代的方式。反转链表的过程, 如果拆解开来, 可以分为下面几步。从拆解的过程可以看出, 反转链表的过程就是依次将head的后面的节点, 放到链表的头部。

1 -> 2 -> 3 -> 4 -> null

2 -> 1 -> 3 -> 4 -> null

3 -> 2 -> 1 -> 4 -> null

4 -> 3 -> 2 -> 1 -> null

const reverseList = function(head: LinkedListNode): LinkedListNode {
    
    let newHead: LinkedListNode = head
    let current: LinkedListNode = head
    
    // current的指针将会向后移动
    function reverse () {
        let a = current.next
        let b = current.next.next
        a.next = head
        current.next = b
        head = a
    }
    
    while (current && current.next) {
       reverse() 
    }
    return head
};

原题地址。我使用的也是笨办法。由于链表头部特殊性，删除头部时需要进行递归(因为在第一次删除头部的节点后, 新的头部也有可能是满足删除条件的节点)。对于其他位置的节点使用常规办法即可。

function removeElements (head: LinkedListNode, val: number): LinkedListNode {

  /**
   * 删除链表的头部
   */
  function deleteHead () {
    head = head.next
    if (head && head.val === val) {
        deleteHead()
    }
  } 

  if (head) {
      if (head.val === val) {
          // 递归删除头部的节点
          deleteHead()
      }

      if (head && head.next) {
        let prevNode = head
        let currentNode = head.next

        while (currentNode) {
          // 删除链表中间符合条件的节点
            if (currentNode.val === val) {
                prevNode.next = currentNode.next
                currentNode = currentNode.next
            } else {
                prevNode = prevNode.next
                currentNode = currentNode.next
            }
        }
      }  
  }
  return head
}

原题地址, 对于这道题目我们就需要运用上之前提到的两种套路(同时保留头部的指针以及当前的节点的指针和虚假的头部)

function oddEvenList (head: LinkedListNode): LinkedListNode {
  let oddHead: LinkedListNode = new LinkedListNode(0)
  let evenHead: LinkedListNode = new LinkedListNode(0)
  let oddTail: LinkedListNode = oddHead
  let evenTail: LinkedListNode = evenHead
  let index: number = 1
  
  while (head) {
      // 链接不同奇偶两条链
      // 这里默认开头是1，所以index从1开始
      if (index % 2 !== 0) {
          oddTail.next = head
          oddTail = oddTail.next
      } else {
          evenTail.next = head
          evenTail = evenTail.next
      }
      head = head.next
      index += 1
  }
  
  // 偶数链的结尾是null，因为是尾部
  evenTail.next = null
  // evenHead.next忽略到假头
  oddTail.next = evenHead.next
  
  // oddHead.next忽略到假头
  return oddHead.next
}

原题地址, 何为所谓的回文链表, 1 -> 2 -> 1 或者 1 -> 1 亦或则 1 -> 2 -> 2 -> 1 可以被称为回文链表。回文链表如果长度为奇数, 那么除去中间点, 两头的链表应当是在反转后应当是相同的。如果是偶数个, 链表的一半经过反转应该等于前半部分。当然有两种情况需要特殊考虑, 比如链表为 1 或者 1 -> 1 的情况下。在排除了这两种特色情况后, 可以通过快慢指针获取链表的中点(fast的速度是slow的两倍)。反转中点之后的链表后, 然后从头部开始和中点开始对比每一个节点的val。

function isPalindrome (head: LinkedListNode): boolean {
  if (!head) {
    return true
  }

  // 通过快慢指针获取中点
  let fast: LinkedListNode = head
  let slow: LinkedListNode = head

  // 链表中点
  let middle = null

  // 循环结束后慢节点就是链表的中点
  while (fast && fast.next && fast.next.next) {
      fast = fast.next.next
      slow = slow.next
  }

  // 一个和两个的情况
  if (fast === slow) {
      if (!fast.next) {
          return true
      } else if ( fast.val === fast.next.val ) {
          return true
      } else {
          return false
      }
  }

  // middle保持对中点的引用
  // slow往后移动
  middle = slow

  // 反转中点以后的链表
  function reverse () {
      let a = slow.next
      let b = slow.next.next
      a.next = middle
      slow.next = b
      middle = a
  }

  while (slow && slow.next) {
      reverse()
  }

  // 从头部和中点开始对比
  while (head && middle) {
      
      if (head.val !== middle.val) {
          return false
      }
      
      head = head.next
      middle = middle.next
      
  }

  return true    
}

原题地址, 对于创建一个新的链表使用的思路就是创建一个虚假的头部, 这道题目的解答也是如此。以及同时保留头部的指针以及尾部的指针, 无论是添加节点还是返回链表都会非常方便。

function mergeTwoLists (l1: LinkedListNode, l2: LinkedListNode): LinkedListNode {
  // 头部的引用
  let newHead: LinkedListNode = new LinkedListNode(0)
  // 尾部的引用
  let newTail: LinkedListNode = newHead
  
  while (l1 && l2) {
    if (l1.val < l2.val) {
        newTail.next = l1
        l1 = l1.next
    } else {
        newTail.next = l2
        l2 = l2.next
    }
    // 始终指向尾部
    newTail = newTail.next
  }
  
  if (!l1) {
    newTail.next = l2
  }
  
  if (!l2) {
    newTail.next = l1
  }
  
  // 忽略虚假的头部
  return newHead.next
}

原题地址。生成虚假的头部后, 两个链表两两相加, 注意进位以及保留位即可。如果val不存在, 取0。

(2 -> 4 -> 3) + (5 -> 6 -> 7 -> 8)

0343

8765

__
9108

function addTwoNumbers (l1: LinkedListNode, l2: LinkedListNode): LinkedListNode {
    let newHead: LinkedListNode = new LinkedListNode(0)
    let newTail: LinkedListNode = newHead
    // carry是进位，8 + 8 = 16 ，进位为1
    let carry: number = 0
    while (l1 || l2) {
        let a: number = l1 ? l1.val : 0
        let b: number = l2 ? l2.val : 0
        // val是保留的位
        let val: number = (a + b + carry) % 10
        carry = Math.floor((a + b + carry) / 10)
        let newNode = new LinkedListNode(val)
        newTail.next = newNode
        newTail = newTail.next
        if (l1) {
            l1 = l1.next
        }
        if (l2) {
            l2 = l2.next
        }
    }
    if (carry !== 0) {
        // 注意最后一位的进位
        let newNode: LinkedListNode = new LinkedListNode(carry)
        newTail.next = newNode
        newTail = newTail.next
    }
    
    return newHead.next
}

原题地址, 通过观察可知, 所谓的旋转就是依次将链表尾部的节点移动到链表的头部, 同时可以发现如果旋转的次数等于链表的长度。链表是没有发生改变的。所以通过提前计算出链表的长度, 可以减少旋转的次数。

输入: 0-> 1-> 2 -> NULL

向右旋转 1 步: 2 -> 0 -> 1 -> NULL
向右旋转 2 步: 1 -> 2 -> 0 -> NULL
向右旋转 3 步: 0 -> 1 -> 2 -> NULL
向右旋转 4 步: 2 -> 0 -> 1 -> NULL

var rotateRight = function(head, k) {
    if (!head || !head.next) {
        return head
    }
    
    let length = 0
    let c = head
    // 计算出链表的长度
    while (c) {
        length += 1
        c = c.next
    }
    
    // 将链表的尾部移动到链表的头部
    // 链表尾部的前一个next指向null
    function rotate () {
        let a = head
        let b = head.next
        while (b && b.next) {
            a = b
            b = b.next
        }
        b.next = head
        head = b
        a.next = null
    }
    
    // 避免没有必要的选装
    let newK = k % length
    let index = 1
    
    while (index <= newK) {
        rotate()
        index += 1
    }
    
    return head
};