ในขณะที่ฉันกำลังทำ LeetCode ฉันสะดุดกับปัญหา 141 เนื่องจากฉันใช้ JavaScript เป็นภาษาโปรแกรมหลักของฉัน ซึ่งไม่มีโครงสร้างข้อมูลแบบ Linked List ฉันจึงพยายามที่จะเข้าใจแนวคิดนี้และหาทางออก LeetCode มีการใช้งาน Linked List สำหรับ JavaScript ในตัว และคุณจะต้องเขียนโซลูชันเท่านั้น ดังนั้นฉันจึงคิดว่า ทำไมไม่ทำให้มันง่ายขึ้นสำหรับคนอื่นๆ ที่อาจประสบปัญหาเดียวกัน บทความนี้อาจช่วยให้คุณเข้าใจแนวคิดบางประการ ดังนั้นโปรดอ่านให้จบ เริ่มต้นด้วยการถามคำถามที่ชัดเจน ...

ลิงค์ลิสต์คืออะไร ?

รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นคล้ายกับอาร์เรย์ อย่างไรก็ตาม ไม่เหมือนกับอาร์เรย์ องค์ประกอบจะไม่ถูกจัดเก็บไว้ในตำแหน่งหน่วยความจำหรือดัชนีเฉพาะ แต่ละองค์ประกอบเป็นวัตถุแยกต่างหากที่มีตัวชี้หรือลิงก์ไปยังวัตถุถัดไปในรายการนั้น

แต่ละองค์ประกอบ (โดยทั่วไปเรียกว่าโหนด) ประกอบด้วยสองรายการ: ข้อมูลที่เก็บไว้และลิงก์ไปยังโหนดถัดไป ข้อมูลสามารถเป็นข้อมูลประเภทใดก็ได้ที่ถูกต้อง คุณสามารถดูได้จากแผนภาพด้านล่าง

ใน JavaScript จะมีลักษณะดังนี้:

const list = {
    head: {
        data: 6
        next: {
            data: 10                                             
            next: {
                data: 12
                next: {
                    data: 3
                    next: null	
                    }
                }
            }
        }
    }
};

class ListNode {
    constructor(data, next = null) {
        this.data = data
        this.next = next               
    }
}

class LinkedList {
    constructor(head = null) {
        this.head = head
    }
}

function getLinkedList (arr){
  const head = arr.reverse().reduce((a,b) => {
  if (!a) {
    a = new ListNode(b);
  } else {
    a = new ListNode(b, a);
  }
  return a;
}, null);

return new LinkedList(head);
}

const list = getLinkedList([2,5,1,7])
console.log(list.head)
// ListNode { data: 2, next: ListNode { data: 5, next: ListNode { data: 1, next: [ListNode] } }}
console.log(list.head.next.data)
// 5

วงจรรายการที่เชื่อมโยงคืออะไร?

วัฏจักรเกิดขึ้นเมื่อ รายการที่เชื่อมโยงไม่เป็นเส้นตรงโดยมีจุดเริ่มต้นและจุดสิ้นสุดอีกต่อไป แต่จะวนเป็นวงวนของโหนดแทน

เราสามารถทำได้โดยชี้โหนดถัดไปของโหนดท้ายไปยังโหนดอื่นในรายการ สมมติว่าเราต้องการให้วงจรเริ่มต้นที่ตำแหน่ง 2 เราสามารถทำได้โดยทำ...

let tail = head
// get the tail
while(tail.next) {
   tail = tail.next
}

// get the cycle node
let pos = 2;
let cycleNode = head
while(pos > 0 && cycleNode.next) {
    cycleNode = cycleNode.next
    pos--
}
// point the next of tail to cycle node
tail.next = cycleNode;

กระต่ายกับเต่า

ปัญหาในการตรวจสอบวงจรในรายการที่เชื่อมโยงอาจดูน่ากลัวในตอนแรก แต่การใช้อัลกอริทึม Floyd's Tortoise and Hareนั้นง่ายต่อการเข้าใจและแก้ไข แนวคิดคือการใช้ตัวชี้ที่ช้าเช่น "เต่า" และตัวชี้ที่เร็วเช่น "กระต่าย" เต่าeเริ่มต้นที่ตำแหน่ง 0 และกระต่ายเริ่มต้นที่ตำแหน่ง 1 ถ้าเต่าเดินไปทีละ 1 ที่ และกระต่ายไปทีละ 2 ที่ ในที่สุดพวกมันก็จะมาพบกันที่ใดที่หนึ่งเป็นวัฏจักร คุณสามารถวาดแต่ละการเคลื่อนไหวเพื่อตรวจสอบได้

ลองนึกภาพวงจรในรายการความยาวที่เชื่อมโยงกันโดยที่ส่วนท้ายชี้ไปที่โหนดที่สองในรายการ

นี่คืออัลกอริทึมที่เราต้องใช้ใน JavaScript

create a slow node pointer and a fast node pointer
while: two pointers exists and fast pointer has a next value
       move the slow pointer by one node and fast pointer by two nodes
       if: at any time, slow pointer equals fast pointer
          linked list contains a cycle.

function hasCycle (head) {
// create 2 pointers
let slow = head;
let fast = head;

while(fast && fast.next){ // while pointers exist and fast pointer has a next value
    fast = fast.next.next; // move fast pointer by two nodes
    slow = slow.next; // move slow pointer by one node
    if(fast === slow) return true; // linked list has a cycle
    }

return false;
}

ความคิดแรกของคุณอาจจะเป็นแค่กลับไปที่โหนดที่กระต่ายกับเต่ามาบรรจบกัน แต่อย่างที่คุณเห็นในภาพประกอบด้านบนวัฏจักรเริ่มต้นที่โหนดที่สองในขณะที่กระต่ายและเต่ามาบรรจบกันที่โหนดที่สาม ดังนั้นมันจะไม่ทำงาน

การแก้ปัญหาจะต้องใช้ตัวชี้ที่สาม หลังจากที่เราพบโหนดที่กระต่ายกับเต่ามาบรรจบกัน เช่น ตัวชี้เร็วเท่ากับตัวชี้ช้า จากนั้นเราจะเลื่อนตัวชี้ช้าและตัวชี้ที่สามไปทีละโหนด และในที่สุดพวกมันก็จะพบกันที่จุดเริ่มของวัฏจักร อัลกอริทึมที่เราต้องใช้ใน JavaScript มีดังนี้

create a slow node pointer and a fast node pointer
while: two pointers exists and fast pointer has a next value
       move the slow pointer by one node and fast pointer by two nodes
       if: at any time, slow pointer equals fast pointer
           stop
if: fast pointer has no next and slow pointer doesnot equals fast pointer
    linked list doesn't contain a cycle
else: 
     while: slow pointer doesn't equal third pointer
            move both slow pointer and third pointer by one node
slow pointer/third pointer is the node where linked list cycle starts.

function cycleNode (head) {
   if(!head || !head.next) return null // head has no next value
    // create 3 pointers
    let fast = head;
    let slow = head;
    let start = head; // third pointer
    
    while(fast && fast.next){ // while pointers exist and fast pointer has a next value
      fast = fast.next.next; // move fast pointer by two nodes
      slow = slow.next; // move slow pointer by one node
      if(fast === slow) break; // stop if slow pointer equals fast pointer
    }
    
    if(slow !== fast) return null // linked list doesn't contain a cycle
    
    while(start !== slow){ // while slow pointer doesn't equal third pointer
      start = start.next; // move third pointer by one node
      slow = slow.next; // move slow pointer by one node
    }
    return start; // where cycle starts
}

ความสงบ.