C++鏈表常見面試考點

  • 鏈表常見問題:
    • 單鏈表找到倒數第n個節點
      • 用兩個指針指向鏈表頭,第一個指針先向前走n步,然後兩個指針同步往前走,當第一個指針指向最後一個節點時,第二個指針就指向了倒數第n個節點。
    • 判斷鏈表有沒有環
      • 快慢指針法,如果有環,那麼兩個指針終會相遇
    • 兩個鏈表是否有重疊
      • 遍歷鏈表長度m,n
      • 長鏈表指針往前走|m – n|步
      • 然後兩個鏈表指針同時往前走,如果有重疊,兩者會在某個時刻相等
    • 鏈表反轉
      • 三個指針:prev,current,next
      • 頭插法