leetcode 鏈表相關(guān)題目解析

harriszh 發(fā)布于2019-08-26 13:38 / 2581人閱讀

摘要：同時保有當(dāng)前鏈表的尾部的指針以及頭部的節(jié)點指針。鏈表可能只有部分成環(huán)這意味著。頭部的引用尾部的引用始終指向尾部忽略虛假的頭部鏈表相加原題地址。生成虛假的頭部后兩個鏈表兩兩相加注意進(jìn)位以及保留位即可。鏈表是沒有發(fā)生改變的。

前言

本文基于leetcode的探索鏈表卡片所編寫。遺憾的是, 我的卡片的進(jìn)度為80%, 依然沒有全部完成。我在探索卡片的時候, 免不了谷歌搜索。并且有一些題目, 我的解答可能不是最優(yōu)解。敬請見諒。

關(guān)于鏈表

鏈表屬于比較簡單的數(shù)據(jù)結(jié)構(gòu), 在這里我在過多的贅述。值的注意的是, 本文都是基于單鏈表的, 雙鏈表的設(shè)計我還沒有實現(xiàn)。

常見的套路

關(guān)于鏈表的算法題目, 我自己總結(jié)了以下幾種套路, 或者說常見的手段

同時保有當(dāng)前節(jié)點的指針, 以及當(dāng)前節(jié)點的前一個節(jié)點的指針。

快慢指針, fast指針的移動速度是slow指針的兩倍, 如果鏈表成環(huán)那么fast和slow必然會相遇。

虛假的鏈表頭, 通過 new ListNode(0), 創(chuàng)建一個虛假的頭部。獲取真正鏈表只需返回head.next(這在需要生成一個新鏈表的時候很有用)。

同時保有當(dāng)前鏈表的尾部的指針, 以及頭部的節(jié)點指針。

善用while循環(huán)。

鏈表的頭部和尾部是鏈表比較特殊的節(jié)點, 需要注意區(qū)別對待

設(shè)計單鏈表

原題的地址, 我在原題的基礎(chǔ)使用了TypeScript模擬實現(xiàn)了鏈表。

鏈表需要擁有以下幾種方法:

get, 根據(jù)鏈表的索引獲取鏈表節(jié)點的value

addAtTail, 添加一個節(jié)點到鏈表的尾部

addAtHead, 添加一個節(jié)點到鏈表的頭部

addAtIndex, 添加一個節(jié)點到鏈表的任意位置

deleteAtIndex, 刪除任意位置的節(jié)點

// 定義鏈表節(jié)點類以及鏈表類的接口
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循環(huán)鏈表, 同時在循環(huán)的過程中使用計數(shù)器計數(shù), 既可以實現(xiàn)
   */
  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
  }

  /**
   * 將新節(jié)點的next屬性指向當(dāng)前的head, 將head指針指向新節(jié)點
   */
  public addAtHead (val: number): void {
    let newNode: LinkedListNode = new LinkedListNode(val, this.head)
    this.head = newNode
    this.length += 1
  }

  /**
   * 將鏈表尾部的節(jié)點的next屬性指向新生成的節(jié)點, 獲取鏈表尾部的節(jié)點需要遍歷鏈表
   */
  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
  }

  /**
   * 這里需要需要運(yùn)用技巧, 遍歷鏈表的同時, 同時保留當(dāng)前的節(jié)點和當(dāng)前節(jié)點的前一個節(jié)點的指針
   */
  public addAtIndex(index: number, val: number): void {
    if (index >= 0 && index <= this.length) {
      let newNode: LinkedListNode = null
      if (index === 0) {
        // 如果index為0, 插入頭部需要與其他位置區(qū)別對待
        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最遠(yuǎn)到達(dá)當(dāng)前鏈表的尾部的節(jié)點，而非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
    }
  }
}

環(huán)形鏈表

原題地址, 將環(huán)形鏈表想象成一個跑道, 運(yùn)動員的速度是肥宅的兩倍, 那么經(jīng)過一段時間后, 運(yùn)動員必然會超過肥宅一圈。這個時候, 運(yùn)動員和肥宅必然會相遇。快慢指針的思想就是源于此。

/**
 * 判斷鏈表是否成環(huán)
 */
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
}

環(huán)形鏈表II

原題地址, 在環(huán)形鏈表的基礎(chǔ)上, 我們需要獲取環(huán)形鏈表的入口。同樣使用快慢指針實現(xiàn)。但是值的注意的是。鏈表可能只有部分成環(huán), 這意味著。快慢指針相遇的點, 可能并不是環(huán)的入口。

慢節(jié)點的運(yùn)動距離為, a + b - c

快節(jié)點的運(yùn)動距離為, 2b + a - c

快節(jié)點的運(yùn)動距離是慢節(jié)點的兩倍。可以得出這個公式 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
    // 快指針移動到入口，并且速度變?yōu)?
    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鏈相交, 那么就會成環(huán)。套用上一題的思路就可以獲取到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  
  } 
}

刪除鏈表的倒數(shù)第N個節(jié)點

原題地址, 這里我使用的是比較笨的辦法, 先計算鏈表的長度, 獲取正序的時n的大小。然后按照刪除鏈表中某一個節(jié)點的方法進(jìn)行刪除即可。需要區(qū)分刪除的是否是第一個。

反轉(zhuǎn)鏈表

原題地址, 常見的反轉(zhuǎn)鏈表的方式就是使用遞歸或者迭代的方式。反轉(zhuǎn)鏈表的過程, 如果拆解開來, 可以分為下面幾步。從拆解的過程可以看出, 反轉(zhuǎn)鏈表的過程就是依次將head的后面的節(jié)點, 放到鏈表的頭部。

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
};

刪除鏈表中的節(jié)點

原題地址。我使用的也是笨辦法。由于鏈表頭部特殊性，刪除頭部時需要進(jìn)行遞歸(因為在第一次刪除頭部的節(jié)點后, 新的頭部也有可能是滿足刪除條件的節(jié)點)。對于其他位置的節(jié)點使用常規(guī)辦法即可。

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

  /**
   * 刪除鏈表的頭部
   */
  function deleteHead () {
    head = head.next
    if (head && head.val === val) {
        deleteHead()
    }
  } 

  if (head) {
      if (head.val === val) {
          // 遞歸刪除頭部的節(jié)點
          deleteHead()
      }

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

        while (currentNode) {
          // 刪除鏈表中間符合條件的節(jié)點
            if (currentNode.val === val) {
                prevNode.next = currentNode.next
                currentNode = currentNode.next
            } else {
                prevNode = prevNode.next
                currentNode = currentNode.next
            }
        }
      }  
  }
  return head
}

奇偶鏈表

原題地址, 對于這道題目我們就需要運(yùn)用上之前提到的兩種套路(同時保留頭部的指針以及當(dāng)前的節(jié)點的指針和虛假的頭部)

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) {
      // 鏈接不同奇偶兩條鏈
      // 這里默認(rèn)開頭是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
  }
  
  // 偶數(shù)鏈的結(jié)尾是null，因為是尾部
  evenTail.next = null
  // evenHead.next忽略到假頭
  oddTail.next = evenHead.next
  
  // oddHead.next忽略到假頭
  return oddHead.next
}

回文鏈表

原題地址, 何為所謂的回文鏈表, 1 -> 2 -> 1 或者 1 -> 1 亦或則 1 -> 2 -> 2 -> 1 可以被稱為回文鏈表。回文鏈表如果長度為奇數(shù), 那么除去中間點, 兩頭的鏈表應(yīng)當(dāng)是在反轉(zhuǎn)后應(yīng)當(dāng)是相同的。如果是偶數(shù)個, 鏈表的一半經(jīng)過反轉(zhuǎn)應(yīng)該等于前半部分。當(dāng)然有兩種情況需要特殊考慮, 比如鏈表為 1 或者 1 -> 1 的情況下。在排除了這兩種特色情況后, 可以通過快慢指針獲取鏈表的中點(fast的速度是slow的兩倍)。反轉(zhuǎn)中點之后的鏈表后, 然后從頭部開始和中點開始對比每一個節(jié)點的val。

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

  // 通過快慢指針獲取中點
  let fast: LinkedListNode = head
  let slow: LinkedListNode = head

  // 鏈表中點
  let middle = null

  // 循環(huán)結(jié)束后慢節(jié)點就是鏈表的中點
  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

  // 反轉(zhuǎn)中點以后的鏈表
  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    
}

合并兩個有序鏈表

原題地址, 對于創(chuàng)建一個新的鏈表使用的思路就是創(chuàng)建一個虛假的頭部, 這道題目的解答也是如此。以及同時保留頭部的指針以及尾部的指針, 無論是添加節(jié)點還是返回鏈表都會非常方便。

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
}

鏈表相加

原題地址。生成虛假的頭部后, 兩個鏈表兩兩相加, 注意進(jìn)位以及保留位即可。如果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是進(jìn)位，8 + 8 = 16 ，進(jìn)位為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) {
        // 注意最后一位的進(jìn)位
        let newNode: LinkedListNode = new LinkedListNode(carry)
        newTail.next = newNode
        newTail = newTail.next
    }
    
    return newHead.next
}

旋轉(zhuǎn)鏈表

原題地址, 通過觀察可知, 所謂的旋轉(zhuǎn)就是依次將鏈表尾部的節(jié)點移動到鏈表的頭部, 同時可以發(fā)現(xiàn)如果旋轉(zhuǎn)的次數(shù)等于鏈表的長度。鏈表是沒有發(fā)生改變的。所以通過提前計算出鏈表的長度, 可以減少旋轉(zhuǎn)的次數(shù)。

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

向右旋轉(zhuǎn) 1 步: 2 -> 0 -> 1 -> NULL
向右旋轉(zhuǎn) 2 步: 1 -> 2 -> 0 -> NULL
向右旋轉(zhuǎn) 3 步: 0 -> 1 -> 2 -> NULL
向右旋轉(zhuǎn) 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
};