บันทึกนี้ถูกจัดเรียงตลอดทั้งสัปดาห์ ฉันหวังว่าจะมีข้อมูลบางอย่างเกี่ยวกับการทดสอบและการสัมภาษณ์เป็นลายลักษณ์อักษร
บทความนี้มีเนื้อหาต่อไปนี้ของรายการที่เชื่อมโยง:
1. การสร้างและการสำรวจรายการที่เชื่อมโยงเดียว
2. ค้นหาจำนวนโหนดในรายการที่เชื่อมโยงเดียว
3. ค้นหาโหนด K-last ในรายการที่เชื่อมโยงเดียว (ดาบชี้ไปที่ข้อเสนอคำถามที่ 15)
4. ค้นหาโหนดกลางในรายการที่เชื่อมโยงเดียว
5. ผสานสองรายการที่เชื่อมโยงเดียวที่สั่งซื้อและรายการที่เชื่อมโยงรวมยังคงอยู่ในลำดับ [ความถี่สูงของการเกิดขึ้น] (ขั้นตอนตามข้อเสนอคำถามที่ 17)
6. การกลับรายการของรายการเชื่อมโยงเดียว [ความถี่สูงสุดของการเกิดขึ้น] (ขั้นตอนตามข้อเสนอคำถามที่ 16)
7. พิมพ์รายการที่เชื่อมโยงเดียวตั้งแต่ปลายถึงจุดเริ่มต้น (ดาบชี้ไปที่ข้อเสนอคำถาม 5)
8. ตรวจสอบว่ารายการที่เชื่อมโยงเดียวมีแหวน
9. นำความยาวของแหวนออกมาในรายการที่เชื่อมโยง
10. ในรายการที่เชื่อมโยงเดียวนำจุดเริ่มต้นของแหวน (ดาบชี้ไปที่ข้อเสนอคำถาม 56) คำถามนี้ต้องใช้คำถาม 8 และ 9 ด้านบน
11. กำหนดจุดตัดแรกของจุดตัดระหว่างสองรายการเชื่อมโยงเดียว (ดาบชี้ไปที่ข้อเสนอคำถามที่ 37)
1. การสร้างและการสำรวจรายการที่เชื่อมโยงเดียว:
Public Class LinkList {Public Node Head; หากส่วนหัวโหนดจุดว่างเปล่าซึ่งหมายความว่ารายการที่เชื่อมโยงยังไม่ได้สร้างขึ้น โหนดและวางไว้ในโหนดปัจจุบันด้านหลัง (เชื่อมโยงโหนดใหม่กับรายการที่เชื่อมโยง) current.next = new node (ข้อมูล); /หลังจากการดำเนินการนี้เสร็จสมบูรณ์แล้วกระแสโหนดจะชี้ไปที่โหนดที่เพิ่มขึ้นใหม่}} // เมธอด โหนดโหนด) {ถ้า node == null) {return;} current = node; {// หมายเหตุ: การอนุญาตของตัวแปรสมาชิกทั้งสองที่นี่ไม่สามารถเป็นได้เนื่องจากการอนุญาตส่วนตัวสามารถเข้าถึงได้ในคลาสนี้เท่านั้น data = data;}} โมฆะคงที่สาธารณะ (String [] args) {LinkList list = new LinkList (); );} list.print (list.head); //ในรหัสข้างต้นโหนดโหนดที่นี่ใช้คลาสภายในเพื่อแสดง (บรรทัดที่ 33) ข้อได้เปรียบที่ใหญ่ที่สุดของการใช้คลาสชั้นในคือพวกเขาสามารถเข้าถึงการดำเนินงานส่วนตัวด้วยชั้นเรียนนอก
หมายเหตุ: ลักษณะของการเข้าถึงคลาสภายในคือ: คลาสภายในสามารถเข้าถึงสมาชิกของคลาสภายนอกโดยตรงรวมถึงคลาสส่วนตัว;
เพื่ออำนวยความสะดวกในการเพิ่มการดำเนินงานและการเดินทางข้ามให้เพิ่มตัวแปรสมาชิกปัจจุบันในคลาส LinkList เพื่อแสดงดัชนีของโหนดปัจจุบัน (บรรทัด 03)
ในวิธีการสำรวจรายการที่เชื่อมโยง (บรรทัด 20) โหนดพารามิเตอร์หมายความว่ามันเริ่มต้นจากโหนดโหนดและไม่จำเป็นต้องผ่านจากโหนดหัว
2. ค้นหาจำนวนโหนดในรายการที่เชื่อมโยงเดียว:
ให้ความสนใจเพื่อตรวจสอบว่ารายการที่เชื่อมโยงนั้นว่างเปล่าหรือไม่ ความซับซ้อนของเวลาคือ o (n) นี่ค่อนข้างง่าย
รหัสหลัก:
// เมธอด: รับความยาวของรายการที่เชื่อมโยงกับ public int getLength (หัวโหนด) {ถ้า (head == null) {return 0; ความยาว th ++;3. ค้นหาโหนด K-last ในรายการที่เชื่อมโยงเดียว:
3.1 ความคิดทั่วไป:
ขั้นแรกให้วนรายการที่เชื่อมโยงทั้งหมดตั้งแต่ต้นจนจบคำนวณขนาดความยาวของรายการที่เชื่อมโยงและรับความยาวของรายการที่เชื่อมโยงมันเป็นเรื่องง่ายที่จะทำ รายการที่เชื่อมโยงนั้นว่างเปล่า k คือ 0, k คือ 1, k มากกว่าจำนวนโหนดในรายการที่เชื่อมโยง
- ความซับซ้อนของเวลาคือ o (n) และแนวคิดทั่วไปมีดังนี้:
Public Int FindLastNode (INT ดัชนี) {// ดัชนีแสดงถึงโหนดของดัชนีไปยังจุดสิ้นสุด ///THE ครั้งแรกที่ฉันสำรวจฉันได้รับความยาวของรายการที่เชื่อมโยงถ้า (head == null) current = head; I <Size - INDEX;ฉันควรทำอย่างไรถ้าผู้สัมภาษณ์ไม่อนุญาตให้คุณสำรวจความยาวของรายการที่เชื่อมโยง? ถัดไปคือ.
3.2 แนวคิดการปรับปรุง: (แนวคิดนี้ใช้ในคำถามอื่น ๆ ด้วย)
ที่นี่คุณต้องประกาศตัวพอยน์เตอร์สองตัวนั่นคือตัวแปรประเภทโหนดสองตัวแรกและครั้งที่สอง ครั้งแรกและที่สองจะถูกคั่นด้วยตำแหน่ง K-1 จากนั้นทั้งสองโหนดจะถูกย้ายไปข้างหลังโดยรวมจนกระทั่งโหนดที่สองถึงโหนดสุดท้ายตำแหน่งที่ชี้ไปที่โหนดแรกคือตำแหน่งของ K-TH จนกระทั่งสุดท้าย โหนด ความซับซ้อนของเวลาคือ o (n)
การใช้งานรหัส: (เวอร์ชันแรก)
โหนดสาธารณะ findlastNode (หัวโหนด, ดัชนี int) {ถ้า (node == null) {return null; 0; ฉัน <ดัชนี; = second.next;} // เมื่อโหนดที่สองว่างการใช้งานรหัส: (เวอร์ชันสุดท้าย) (โยนข้อยกเว้นเมื่อ K มากกว่าจำนวนโหนดในรายการที่เชื่อมโยง)
ในรหัสข้างต้นฟังก์ชั่นดูเหมือนว่าจะถูกนำไปใช้ แต่ก็ไม่แข็งแรงพอ:
ให้ความสนใจกับสถานการณ์ที่ k เท่ากับ 0;
หาก K มากกว่าจำนวนโหนดในรายการที่เชื่อมโยงจะมีการรายงานข้อยกเว้นตัวชี้โมฆะดังนั้นจึงจำเป็นต้องมีการตัดสินที่นี่
รหัสหลักมีดังนี้:
โหนดสาธารณะ FindLastNode (หัวโหนด, int k) {ถ้า (k == 0 || head == null) {return null; ตำแหน่งสำหรับ (int i = 0; i <k - 1; i ++) {system.out.println ("ค่าของฉันคือ"+i); ค่าของ K มากกว่าความยาวของรายการที่เชื่อมโยง // โยน nullpointerexception ใหม่ ("ความยาวของรายการที่เชื่อมโยงน้อยกว่า" + k); NULL; โหนดที่สองถึงโหนดสุดท้ายในเวลานี้โหนดที่ชี้ไปที่ครั้งแรกคือโหนดที่เรากำลังมองหา4. ค้นหาโหนดกลางในรายการที่เชื่อมโยงเดียว:
ในทำนองเดียวกันผู้สัมภาษณ์ไม่อนุญาตให้คุณคำนวณความยาวของรายการที่เชื่อมโยง
ความคิด:
เช่นเดียวกับส่วนที่สองด้านบนตัวชี้สองตัวถูกตั้งค่าเป็นครั้งแรกและที่สอง แต่ที่นี่ตัวชี้สองตัวเลื่อนไปข้างหน้าในเวลาเดียวกันตัวชี้ที่สองใช้เวลาสองขั้นตอนในแต่ละครั้ง ที่โหนดสุดท้ายโหนดที่ชี้ไปที่ตัวชี้แรกคือโหนดกลาง โปรดทราบว่ารายการที่เชื่อมโยงนั้นว่างเปล่าและจำนวนโหนดของรายการที่เชื่อมโยงคือ 1 และ 2 ความซับซ้อนของเวลาคือ o (n)
การใช้รหัส:
// วิธีการ: ค้นหาโหนดกลางของรายการที่เชื่อมโยงกับโหนดสาธารณะ findMidNode (หัวโหนด) {ถ้า (head == null) {return null; จุดที่สองจุดเคลื่อนที่สองหลักโหนดแรกจะเคลื่อนที่หนึ่งขณะที่ (วินาที! = null && second.next! = null) {first = first.next; เพื่อเป็นโมฆะในเวลานี้ตำแหน่งที่ชี้ไปที่ตัวชี้แรกคือตำแหน่งของโหนดกลางส่งคืนก่อน;ในรหัสข้างต้นเมื่อ n เป็นตัวเลขคู่โหนดที่ได้รับคือ N/2 + 1 โหนด ตัวอย่างเช่นเมื่อมี 6 โหนดในรายการที่เชื่อมโยงจะได้รับโหนดที่สี่
5. ผสานสองรายการที่เชื่อมโยงเดียวที่สั่งซื้อและรายการที่เชื่อมโยงรวมยังคงอยู่ในลำดับ:
คำถามนี้มักถูกตรวจสอบโดย บริษัท ต่าง ๆ
ตัวอย่างเช่น:
รายการ 1:
1-> 2-> 3-> 4
รายการ 2:
2-> 3-> 4-> 5
หลังจากผสาน:
1-> 2-> 2-> 3-> 3-> 4-> 4-> 5
แนวคิดการแก้ปัญหา:
เปรียบเทียบรายการที่เชื่อมโยง 1 และรายการที่เชื่อมโยง 2 ถัดจากกัน
สิ่งนี้คล้ายกับการเรียงลำดับรวม ให้ความสนใจเป็นพิเศษกับสถานการณ์ที่ทั้งสองรายการที่เชื่อมโยงว่างเปล่าและหนึ่งในนั้นว่างเปล่า จำเป็นต้องใช้พื้นที่ O (1) เท่านั้น ความซับซ้อนของเวลาคือ O (สูงสุด (LEN1, LEN2))
การใช้รหัส:
// พารามิเตอร์ทั้งสองแสดงถึงโหนดส่วนหัวของสองรายการที่เชื่อมโยงกับโหนดสาธารณะ mergelinkList (โหนด head1, โหนด head2) {ถ้า (head1 == null && head2 == null) {// ถ้าทั้งสองรายการที่เชื่อมโยงนั้นว่างเปล่า if (head1 == null) {return head2; รายการ // ที่จุดเริ่มต้นเราปล่อยให้โหนดปัจจุบันชี้ไปที่ข้อมูลขนาดเล็กใน head1 และ head2 และรับโหนดหัวถ้า (head1.data <head2.data) {head = head1; ถัดไป;} else {head = head2; ; current.next; (head2! = null) {// ระบุว่ารายการที่เชื่อมโยง 1 หลังจากผ่านไปแล้วมันว่างเปล่า. next = head2;การทดสอบรหัส:
โมฆะสาธารณะคงที่ (สตริง [] args) {linklist list1 = new LinkList (); (i);} สำหรับ (int i = 3; i <8; i ++) {list2.add (i); );วิธีการเพิ่มและวิธีการพิมพ์ที่ใช้ในรหัสด้านบนสอดคล้องกับส่วนย่อย 1
เอฟเฟกต์การทำงาน:
หมายเหตุ: การแก้ปัญหานั้นเรียกซ้ำใน "ข้อเสนอการชี้ดาบ" ซึ่งรู้สึกยากที่จะเข้าใจ
6. การผกผันของรายการเชื่อมโยงเดียว: [ความถี่สูงสุดของการเกิดขึ้น]
ตัวอย่างเช่นรายการที่เชื่อมโยง:
1-> 2-> 3-> 4
หลังจากการผกผัน:
4-> 2-> 2-> 1
ความคิด:
วนซ้ำผ่านรายการที่เชื่อมโยงต้นฉบับตั้งแต่ต้นจนจบและแต่ละโหนดจะถูกสำรวจและจะถูกลบออกและวางไว้ที่ส่วนหน้าของรายการที่เชื่อมโยงใหม่ โปรดทราบว่ารายการที่เชื่อมโยงนั้นว่างเปล่าและมีเพียงโหนดเดียว ความซับซ้อนของเวลาคือ o (n)
วิธีที่ 1: (Traversal)
// วิธีการ: การกลับรายการของรายการที่เชื่อมโยงโหนดสาธารณะ Reverselist (หัวโหนด) {// ถ้ารายการที่เชื่อมโยงว่างเปล่าหรือมีเพียงโหนดเดียวไม่จำเป็นต้องมีการผกผันและโหนดหัวของรายการที่เชื่อมโยงเดิมจะถูกส่งกลับโดยตรงไปยัง รายการที่เชื่อมโยงกันถ้า (head == null || head.next == null) {return head;} node current = head; ส่วนหัวของรายการที่เชื่อมโยงใหม่หลังจากการผกผัน (ปัจจุบัน! = null) {next = current.next; โหนดถัดไปของกระแสไปยังโหนดส่วนหัวของรายการที่เชื่อมโยงใหม่ reversehead = ปัจจุบัน;ในรหัสข้างต้นรหัสหลักคือบรรทัดที่ 16 และ 17
วิธีที่ 2: (การเรียกซ้ำ)
วิธีนี้ค่อนข้างยากดังนั้นฉันจะไม่พูดถึงเรื่องนี้ในตอนนี้
7. พิมพ์รายการที่เชื่อมโยงเดียวตั้งแต่ต้นจนจบ:
สำหรับคำสั่งแบบคว่ำประเภทนี้เราควรนึกถึงสแต็คก่อนและออกก่อน ดังนั้นคำถามนี้อาจใช้สแต็คด้วยตัวเองหรือปล่อยให้ระบบใช้สแต็กนั่นคือการเรียกซ้ำ ให้ความสนใจกับกรณีที่รายการที่เชื่อมโยงว่างเปล่า ความซับซ้อนของเวลาคือ o (n)
หมายเหตุ: อย่าคิดเกี่ยวกับการย้อนกลับรายการที่เชื่อมโยงเดียวก่อนจากนั้นสำรวจผลลัพธ์
วิธีที่ 1: (สร้างสแต็คใหม่ด้วยตัวเอง)
// วิธีการ: พิมพ์รายการเดียวที่เชื่อมโยงจากปลายสุดของโมฆะสาธารณะ reverseprint (หัวโหนด) {ถ้า (head == null) {return; สร้างโหนดสแต็กใหม่ Cur Rent = Head; // กดสแต็กโหนดพิมพ์ออกมาในขณะที่ (stack.size ()> 0) {system.out.println (stack.pop (). ข้อมูล);วิธีที่ 2: (ใช้สแต็กของระบบ: รหัสซ้ำสง่างามและรัดกุม)
โมฆะสาธารณะ Reverseprint (หัวโหนด) {ถ้า (head == null) {return;} reverseprint (head.next);สรุป: วิธีที่ 2 ขึ้นอยู่กับการใช้งานซ้ำ สแต็คที่ชัดเจนของวิธีการ 1 ถูกนำมาใช้ตามลูปและรหัสมีความแข็งแกร่งมากขึ้น
8. ตรวจสอบว่ารายการที่เชื่อมโยงเดียวมีแหวนหรือไม่:
พอยน์เตอร์สองตัวยังใช้ที่นี่
ดังนั้นเราใช้พอยน์เตอร์สองตัวเพื่อสำรวจ: ตัวชี้แรกใช้เวลาทีละขั้นตอนและตัวชี้ที่สองใช้เวลาสองขั้นตอนในแต่ละครั้ง ความซับซ้อนของเวลาคือ o (n)
วิธี:
// วิธีการ: พิจารณาว่ารายการที่เชื่อมโยงกันเดียวมีบูลีน Public Boolean (หัวโหนด) {ถ้า (head == null) {return false; ) {First = First.next; แหวนส่งคืนจริง;รหัสเวอร์ชันเต็ม: (รวมถึงส่วนทดสอบ)
ที่นี่เราต้องเพิ่มวิธีการเพิ่มมากเกินไป (โหนดโหนด) ซึ่งควรใช้เมื่อสร้างรายการที่เชื่อมโยงแบบวงกลมทางเดียว
LinkList.java: LinkList ระดับสาธารณะ {หัวโหนดสาธารณะ; ll) { / / /ถ้าโหนดส่วนหัวว่างเปล่าหมายความว่ารายการที่เชื่อมโยงยังไม่ได้สร้างขึ้นจากนั้นกำหนดโหนดใหม่ให้กับหัวโหนดส่วนหัว = โหนดใหม่ (ข้อมูล); สร้างโหนดใหม่วางไว้ด้านหลังโหนดปัจจุบัน (เชื่อมโยงโหนดใหม่กับรายการที่เชื่อมโยง) current.next = new node (data); ; ; โหนด) {ถ้า node == null) {return;} current = node; วิธีการ: ตรวจพบว่ารายการที่เชื่อมโยงกันเดียวมีบูลีนสาธารณะ Ring (N Ode Head) {ถ้า (head == null) {return false;} node first = head; First = First.next; รายการมีแหวนส่งคืนจริง;}} return false; ข้อมูล int; เพิ่มข้อมูลไปยัง LinkList สำหรับ (int i = 0; i <4; i ++) {list.add (i);}} list.add (list.head); เป็นลูปในรายการที่เชื่อมโยง หมายเหตุ: โครงสร้างของแหวนที่ได้รับในเวลานี้คือโครงสร้างของรูปที่ 1 ในส่วนต่อไปนี้ 8 System.out.println (list.hascycle (list.head));รหัสที่ตรวจพบว่ารายการที่เชื่อมโยงเดียวมีวงแหวนคือบรรทัด 50 หรือไม่
บรรทัดที่ 88: เรายังคงเพิ่มโหนดส่วนหัวไปยังรายการที่เชื่อมโยงและรายการที่เชื่อมโยงเดียวจะถูกวนในเวลานี้ เอฟเฟกต์การวิ่งครั้งสุดท้ายเป็นจริง
หากมีการลบรหัส 88 บรรทัดรายการที่เชื่อมโยงเดียวจะไม่มีลูปในเวลานี้และเอฟเฟกต์การรันเป็นเท็จ
9. นำรายการที่เชื่อมโยงกับวงแหวนความยาวของวงแหวน:
รายการลิงค์ที่เราพบมักจะพบมีดังต่อไปนี้: (รูปที่ 1)
ความยาวของวงแหวนในภาพด้านบนคือ 4
แต่เป็นไปได้ว่าสิ่งต่อไปนี้มีดังต่อไปนี้: (รูปที่ 2)
ในเวลานี้ความยาวของแหวนในภาพด้านบนคือ 3
แล้วคุณจะพบความยาวของแหวนได้อย่างไร?
ความคิด:
ที่นี่เราต้องใช้วิธีการ Hascycle ในส่วนที่ 7 ด้านบน (วิธีการตรวจสอบว่ามีแหวนในรายการที่เชื่อมโยง) มันส่งคืนค่าสำหรับโหนดที่เราพบกัน จากนั้นเราสามารถรับโหนดที่เราพบกันได้
วิธี:
// วิธีการ: พิจารณาว่ารายการที่เชื่อมโยงเดียวมีแหวนหรือไม่ โหนดที่ส่งคืนเป็นโหนดที่ตรงกับโหนดสาธารณะ Hascycle (หัวโหนด) {ถ้า (head == null) {return null; .Next; null;} // วิธีการ: มีรายการที่เชื่อมโยงวงแหวนเพื่อให้ได้ความยาวของแหวน โหนดพารามิเตอร์แสดงถึงโหนดที่ตรงกับ int public int getCycleLength (โหนดโหนด) {ถ้า (head == null) {return 0; current.next;รหัสเวอร์ชันเต็ม: (รวมถึงส่วนทดสอบ)
LINKLIST ระดับสาธารณะ {หัวโหนดสาธารณะ; โหนดนั้นว่างเปล่าหมายความว่ารายการที่เชื่อมโยงยังไม่ได้สร้างขึ้นจากนั้นกำหนดโหนดใหม่ให้กับส่วนหัว Node Head = NEW NODE (ข้อมูล); โหนดปัจจุบัน (เชื่อมโยงโหนดใหม่กับรายการที่เชื่อมโยง) current.next = new node (ข้อมูล); โหนดปัจจุบันชี้ไปที่โหนดที่เพิ่มขึ้นใหม่}} // เมธอดโอเวอร์โหลด: เพิ่มโหนดลงในรายการที่เชื่อมโยงกับโมฆะสาธารณะเพิ่ม (โหนดโหนด) {ถ้า (node == null) {return;} ถ้า (head = = null) {head = node; จากโหนดโหนดโมฆะพิมพ์ (โหนดโหนด) {ถ้า (node == null) {return;} current = node; current.next;}} // วิธีการ: พิจารณาว่ารายการที่เชื่อมโยงเดียวมีแหวน First = head; รายการที่เชื่อมโยงคือการส่งคืนแบบแหวนก่อน; โหนดพารามิเตอร์แสดงถึงโหนดที่ตรงกับ int public int getCycleLength (โหนดโหนด) {ถ้า (head == null) {return 0; current.next; ส่วนตัวเนื่องจากการอนุญาตของส่วนตัวสามารถเข้าถึงได้สำหรับชั้นเรียนนี้เท่านั้น ข้อมูล int; = null; ; กระบวนการคือโครงสร้างของรูปที่ 2 ในส่วนนี้โหนดปัจจุบัน = list1.hascycle (list1.head); ));}}เอฟเฟกต์การทำงาน:
หากรหัสทดสอบด้านบนของบรรทัด 104 เป็น 122 ถูกเปลี่ยนเป็นต่อไปนี้: (เช่นเปลี่ยนโครงสร้างในรูปที่ 2 เป็นโครงสร้างในรูปที่ 1)
โมฆะสาธารณะคงที่ (สตริง [] args) {linklist list1 = new LinkList (); (list1.head); หมายเหตุ: โครงสร้างของวงแหวนนี้ที่ได้รับในเวลานี้คือโครงสร้างของรูปที่ 1 ในส่วนนี้ Node Current = list1.hascycle (list1.head);เรียกใช้ผลลัพธ์:
หากคุณลบบรรทัดที่ 8 ในรหัสด้านบนรายการที่เชื่อมโยงไม่มีลูปดังนั้นผลลัพธ์ของการทำงานคือ 0
10. ในรายการที่เชื่อมโยงเดียวจุดเริ่มต้นของวงแหวนสกัด:
รายการลิงค์ที่เราพบมักจะพบมีดังต่อไปนี้: (รูปที่ 1)
จุดเริ่มต้นที่ 1 ของแหวนในภาพด้านบน
แต่เป็นไปได้ว่าสิ่งต่อไปนี้มีดังต่อไปนี้: (รูปที่ 2)
ในเวลานี้จุดเริ่มต้นของแหวนในภาพด้านบนคือ 2
วิธีที่ 1:
ที่นี่เราจำเป็นต้องใช้วิธีการกำจัดความยาวของวงแหวนในส่วนที่ 8 ด้านบนเพื่อ getCycleLength และใช้วิธีนี้เพื่อให้ได้ความยาวของวงแหวน หลังจากได้รับความยาวของวงแหวนสองตัวชี้ตัวชี้ที่หนึ่งและครั้งที่สอง พบกันปมเมื่อพวกเขาพบกัน
หมายเหตุ: เพื่อค้นหาจุดเริ่มต้นของวงแหวนเราต้องได้รับความยาวของวงแหวนก่อนและเพื่อให้ได้ความยาวของวงแหวนเราต้องพิจารณาก่อนว่ามีวงแหวนหรือไม่ ดังนั้นจึงมีสามวิธีที่ใช้ที่นี่
การใช้รหัส:
รหัสหลักสำหรับวิธีการ 1:
// วิธี: รับจุดเริ่มต้นของแหวน ความยาวพารามิเตอร์แสดงถึงความยาวของโหนดสาธารณะ GetCyclestart (หัวโหนด, int cyclelelengt) {ถ้า (head == null) {return null; ถึงขั้นตอนความยาวสำหรับ (int i = 0; i <cyclelength; i ++) {second = second.next; ! = null) {First = First.next; คืนค่า null;รหัสเวอร์ชันเต็ม: (รวมถึงส่วนทดสอบ)
LINKLIST ระดับสาธารณะ {หัวโหนดสาธารณะ; โหนดนั้นว่างเปล่าหมายความว่ารายการที่เชื่อมโยงยังไม่ได้สร้างขึ้นจากนั้นกำหนดโหนดใหม่ให้กับส่วนหัว Node Head = NEW NODE (ข้อมูล); โหนดปัจจุบัน (เชื่อมโยงโหนดใหม่กับรายการที่เชื่อมโยง) current.next = new node (ข้อมูล); โหนดปัจจุบันชี้ไปที่โหนดที่เพิ่มขึ้นใหม่}} // เมธอดโอเวอร์โหลด: เพิ่มโหนดลงในรายการที่เชื่อมโยงกับโมฆะสาธารณะเพิ่ม (โหนดโหนด) {ถ้า (node == null) {return;} ถ้า (head = = null) {head = node; จากโหนดโหนดโมฆะพิมพ์ (โหนดโหนด) {ถ้า (node == null) {return;} current = node; current.next;}} // วิธีการ: พิจารณาว่ารายการที่เชื่อมโยงเดียวมีแหวน First = head; รายการที่เชื่อมโยงคือการส่งคืนแบบแหวนก่อน; โหนดพารามิเตอร์แสดงถึงโหนดที่ตรงกับ int public int getCycleLength (โหนดโหนด) {ถ้า (head == null) {return 0; current.next; ความยาวพารามิเตอร์แสดงถึงความยาวของโหนดสาธารณะ GetCyclestart (หัวโหนด, int cyclelelengt) {ถ้า (head == null) {return null; ถึงขั้นตอนความยาวสำหรับ (int i = 0; i <cyclelength; i ++) {second = second.next; ! = null) {First = First.next; ส่งคืน null;} โหนดคลาส {// note: นี่คือการอนุญาตของตัวแปรสมาชิกสองตัวในเวลานั้นไม่สามารถเป็นส่วนตัวได้เนื่องจากการอนุญาตของส่วนตัวสามารถเข้าถึงได้ในคลาสนี้เท่านั้น ข้อมูล int; = null; ; เวลาคือโครงสร้างของรูปที่ 2 ในส่วนนี้โหนดปัจจุบัน = list1.hascycle (list1.head); .out.println ("จุดเริ่มต้นของแหวนคือ" + list1.getCyclestart (list1.head, ความยาว) .data);11. กำหนดจุดสี่แยกแรกที่สองรายการเชื่อมโยงเดี่ยวตัดกัน:
"ความงามของการเขียนโปรแกรม" p193, 5.3, คำถามสัมภาษณ์ 37 มีคำถามนี้
ในระหว่างการสัมภาษณ์ปฏิกิริยาแรกของคนจำนวนมากเมื่อพบกับคำถามนี้คือ: สำรวจแต่ละโหนดตามลำดับในรายการที่เชื่อมโยงครั้งแรก หากมีโหนดในรายการที่เชื่อมโยงที่สองเช่นเดียวกับโหนดในรายการที่เชื่อมโยงครั้งแรกหมายความว่ารายการที่เชื่อมโยงทั้งสองทับซ้อนกันที่โหนดนี้ เห็นได้ชัดว่าความซับซ้อนของเวลาของวิธีนี้คือ O (LEN1 * LEN2)
วิธีที่ 1: ความคิดในการใช้สแต็ก
เราสามารถเห็นรายการที่เชื่อมโยงสองรายการที่มีโหนดทั่วไปและซ้อนทับบางส่วนรูปร่างทอพอโลยีดูเหมือน y แต่มันไม่สามารถเป็นรูปตัว X ได้ ดังที่แสดงในรูปด้านล่าง:
ดังที่แสดงในรูปด้านบนหากรายการที่เชื่อมโยงเดียวมีโหนดทั่วไปแล้วโหนดสุดท้าย (โหนด 7) จะต้องเหมือนกันและเริ่มจากโหนดหนึ่งที่อยู่ตรงกลาง (โหนด 6) และ โหนดที่ตามมาจะเหมือนกัน
ปัญหาตอนนี้คือในรายการที่เชื่อมโยงเดียวเราสามารถข้ามตามลำดับจากโหนดเริ่มต้นและในที่สุดก็ถึงโหนดปลาย โหนดหางสุดท้ายที่มาถึงจะถูกเปรียบเทียบครั้งแรก ดังนั้นเราสามารถนึกถึงการใช้คุณสมบัติของสแต็กเพื่อแก้ปัญหานี้: วางโหนดของรายการที่เชื่อมโยงทั้งสองไว้ในสองสแต็คเพื่อให้โหนดสุดท้ายของรายการที่เชื่อมโยงทั้งสองอยู่ที่ด้านบนของทั้งสองสแต็ก มาเปรียบเทียบกัน
ด้วยวิธีนี้เราจำเป็นต้องใช้สแต็คเสริมสองกองความซับซ้อนของพื้นที่คือ O (LEN1+LEN2) และความซับซ้อนของเวลาคือ O (LEN1+LEN2) เมื่อเทียบกับวิธีการใช้กำลังเดรัจฉานในตอนแรกประสิทธิภาพเวลาได้รับการปรับปรุงซึ่งเทียบเท่ากับการใช้การใช้พื้นที่เพื่อประสิทธิภาพเวลา
แล้วมีวิธีที่ดีกว่านี้ไหม? มาพูดถึงเรื่องต่อไป
วิธีที่ 2: กำหนดโหนดแรกที่มีสองรายการที่เชื่อมโยงกันข้าม: ใช้ตัวชี้ที่รวดเร็วและช้าแนะนำ (โซลูชันที่ดีที่สุด)
ในวิธีที่ 2 ด้านบนเหตุผลที่เราใช้สแต็กเป็นเพราะเราต้องการสำรวจไปยังโหนดท้ายของรายการที่เชื่อมโยงทั้งสองในเวลาเดียวกัน其实为解决这个问题我们还有一个更简单的办法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走|len1-len2| 步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个交点。
这种思路的时间复杂度也是O(len1+len2)，但是我们不再需要辅助栈，因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候，就可以动手写代码了。
核心代码：
//方法：求两个单链表相交的第一个交点public Node getFirstCommonNode(Node head1, Node head2) { if (head1 == null || head == null) { return null; } int length1 = getLength(head1); int length2 = getLength(head2); int lengthDif = 0; //两个链表长度的差值Node longHead; Node shortHead; //找出较长的那个链表if (length1 > length2) { longHead = head1; shortHead = head2; lengthDif = length1 - length2; } else { longHead = head2; shortHead = head1; lengthDif = length2 - length1; } //将较长的那个链表的指针向前走length个距离for (int i = 0; i < lengthDif; i++) { longHead = longHead.next; } //将两个链表的指针同时向前移动while (longHead != null && shortHead != null) { if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点return longHead; } longHead = longHead.next; shortHead = shortHead.next; } return null; } //方法：获取单链表的长度public int getLength(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length;以上就是有关java链表的经典面试题目，希望可以帮助大家顺利通过面试。