تم فرز هذه الملاحظة لمدة أسبوع كامل. آمل أن أحصل على بعض المعلومات حول الاختبار المكتوب والمقابلة.
تحتوي هذه المقالة على محتويات القائمة المرتبطة التالية:
1. إنشاء قوائم واحدة مرتبطة ومرتبطة
2. ابحث عن عدد العقد في قائمة واحدة مرتبطة
3. ابحث عن عقدة K-Last في قائمة واحدة مرتبطة (سيف يشير إلى تقديمه ، السؤال 15)
4. ابحث عن العقد الوسيطة في قائمة واحدة مرتبطة
5. دمج قوائم مرتبطة مفردة مرتبة ، ولا تزال القوائم المرتبطة المدمجة بالترتيب [التردد العالي للحدوث] (خطوة من العرض ، السؤال 17)
6. انعكاس القائمة المفردة المرتبطة [أعلى تردد للحدوث] (خطوة من خلال العرض ، السؤال 16)
7. اطبع قائمة واحدة مرتبطة من النهاية إلى البداية (يشير السيف إلى تقديمه ، السؤال 5)
8. تحديد ما إذا كانت القائمة المرتبطة واحدة لها حلقة
9. أخرج طول الحلقة في القائمة المرتبطة
10. في القائمة المرتبطة الفردية ، أخرج نقطة انطلاق الحلبة (يشير السيف إلى تقديمه ، السؤال 56). يحتاج هذا السؤال إلى استخدام الأسئلة 8 و 9 أعلاه.
11. حدد نقطة التقاطع الأولى للتقاطع بين قائمتين متصلتين (سيوف يشير إلى تقديمه ، السؤال 37)
1. إنشاء وتجاوز القوائم المرتبطة المفردة:
LinkList Public Class {Public Node Head ؛ إذا كانت النقطة فارغة ، مما يعني أنه لم يتم إنشاء القائمة المرتبطة بعد. العقدة ووضعها في العقدة الحالية (ربط العقدة الجديدة مع القائمة المرتبطة) Current.next = New Node (Data) ؛ /بعد اكتمال هذه العملية ، تشير العقدة الحالية إلى العقدة المضافة حديثًا}} // الطريقة: اجتياز القائمة المرتبطة (طباعة القائمة المرتبطة. تشير المعلمات للطريقة إلى أن التجارة تبدأ من طباعة الفراغ العام العقدة ( العقدة) {if (node == null) {return ؛ {// ملاحظة: لا يمكن أن تكون أذونات المتغيرين هنا لأن الأذونات الخاصة يمكن الوصول إليها فقط من هذه الفئة. البيانات = البيانات ؛ ) ؛في الكود أعلاه ، تستخدم عقدة العقدة هنا فئة داخلية لتمثيلها (الأسطر 33). أكبر ميزة لاستخدام الفصول الداخلية هي أنه يمكنهم الوصول إلى بعضهم البعض من العمليات الخاصة مع الطبقات الخارجية.
ملاحظة: يمكن لخصائص الوصول إلى الفئة الداخلية: يمكن للفصول الداخلية الوصول مباشرة إلى أعضاء الفصول الخارجية ، بما في ذلك الفئات الخارجية ؛
لتسهيل عمليات الإضافة والمرور ، أضف متغير عضو إلى فئة LinkList لتمثيل فهرس العقدة الحالية (السطر 03).
في طريقة اجتياز القائمة المرتبطة (السطر 20) ، تعني عقدة المعلمة أنها تبدأ من عقدة العقدة ، ولا تحتاج بالضرورة إلى اجتياز عقدة الرأس.
2. ابحث عن عدد العقد في قائمة واحدة مرتبطة:
انتبه للتحقق مما إذا كانت القائمة المرتبطة فارغة. التعقيد الوقت هو o (n). هذا بسيط نسبيا.
الكود الأساسي:
//طريقة: طول القائمة المفردة المفرطة (رأس العقدة) {if (head == null) {return 0 ؛ الطول ++ ؛3. ابحث عن العقدة K-Last في قائمة واحدة مرتبطة:
3.1 الأفكار العادية:
أولاً ، قم بتكرار القائمة المرتبطة بأكملها من البداية إلى النهاية ، وحساب حجم الطول للقائمة المرتبطة ، واحصل على طول القائمة المرتبطة ، فمن السهل القيام به فقط. القائمة المرتبطة فارغة ، k هي 0 ، k هي 1 ، k أكبر من عدد العقد في القائمة المرتبطة
). التعقيد الزمني هو o (n) ، والفكرة العامة هي كما يلي:
Public Int FindLastnode (int index) {// index يمثل عقدة الفهرس إلى النهاية. Current = There (Current! = null) {size ++ ؛ i <sively - index ؛ما الذي يجب أن أفعله إذا لم يسمح لك المقابلة بتجاوز طول القائمة المرتبطة؟ التالي.
3.2 أفكار التحسين: (هذه الفكرة تستخدم أيضًا في أسئلة أخرى)
هنا تحتاج إلى إعلان اثنين من المؤشرات: وهذا هو ، المتغيرات من النوعين أولاً والثاني. يتم فصل الأول والثاني بواسطة مواضع K-1 ، ثم يتم نقل العقدتين للخلف ككل حتى تصل العقدة الثانية العقدة. تعقيد الوقت هو o (n)
تنفيذ الكود: (الإصدار الأول)
العقدة العامة findlastnode (head node ، int) {if (node == null) {return null ؛ 0 ؛ = Second.next ؛تنفيذ الكود: (الإصدار النهائي) (رمي استثناء عندما يكون K أكبر من عدد العقد في القائمة المرتبطة)
في الكود أعلاه ، يبدو أن الوظيفة قد تم تنفيذها ، لكنها ليست قوية بما فيه الكفاية:
انتبه إلى الوضع الذي يساوي K 0 ؛
إذا كان K أكبر من عدد العقد في القائمة المرتبطة ، فسيتم الإبلاغ عن استثناء مؤشر فارغ ، لذلك هناك حاجة إلى حكم هنا.
الرمز الأساسي هو كما يلي:
العقدة العامة findlastnode (head int k) {if (k == 0 || head == null) {return null ؛ موقف (int i = 0 ؛ i <k - 1 ؛ i ++) {system.out.println ( تكون قيمة K أكبر بالفعل من طول القائمة المرتبطة // رمي NullPointerException ("طول القائمة المرتبطة أقل من" + K) ؛ NULL ؛ تصل العقدة الثانية إلى العقدة الأخيرة ، والتي أشار إليها العقدة التي نبحث عنها أولاً ؛4. ابحث عن العقد الوسيطة في قائمة واحدة مرتبطة:
وبالمثل ، لا يسمح لك المقابلة بحساب طول القائمة المرتبطة.
فكرة:
مثل القسم الثاني أعلاه ، يتم تعيين مؤشران في المركز الأول والثاني ، ولكن هنا ، يتحرك المؤشران للأمام في نفس الوقت ، يأخذ المؤشر الثاني خطوتين في كل مرة ، ويأخذ المؤشر الأول خطوة واحدة في كل مرة حتى يصل المؤشر الثاني في العقدة الأخيرة ، تشير العقدة التي أشار إليها المؤشر الأول هي العقدة المتوسطة. لاحظ أن القائمة المرتبطة فارغة وأن عدد العقد في القائمة المرتبطة هو 1 و 2. التعقيد الوقت هو o (n).
تنفيذ الكود:
// الطريقة: العثور على العقدة الوسيطة للعقدة العامة المرتبطة (Head) {if (head == null) {return null ؛ النقطة الثانية تحرك رقمين ، تتحرك العقدة الأولى (الثانية! = NULL && second.next! = null) {first.next ؛ إلى NULL في هذا الوقت ، فإن الموقف الذي أشار إليه المؤشر الأول هو موضع العقدة الوسيطة أولاً ؛في الكود أعلاه ، عندما يكون 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 (Max (LEN1 ، LEN2))
تنفيذ الكود:
. if (head1 null) {return head2 ؛ قائمة // في البداية ، سمحت للعقدة الحالية إلى البيانات الأصغر في Head1 و Head2 ، والحصول على عقدة الرأس إذا كان (Head1.data <head2.data) {head1 ؛ التالي ؛ ؛ Current.ext ؛ (head2! = null) {// تشير إلى أن القائمة المرتبطة 1 بعد عبورها ، فهي فارغة.اختبار الكود:
static static void (string [] args) {LinkList List1 = New LinkList () ؛ (i) ؛ ) ؛تتوافق طريقة ADD وطريقة الطباعة المستخدمة في الكود أعلاه مع القسم الفرعي 1.
تأثير الجري:
ملاحظة: الحل متكرر في "عرض السيف" ، والذي يشعر صعوبة بعض الشيء في الفهم.
6. انعكاس قائمة واحدة مرتبطة: [أعلى تردد للحدوث]
على سبيل المثال ، القائمة المرتبطة:
1-> 2-> 3-> 4
بعد الانقلاب:
4-> 2-> 2-> 1
فكرة:
تكرار من خلال القائمة المرتبطة الأصلية من البداية إلى النهاية ، ويتم اجتياز كل عقدة ، ويتم إزالتها ووضعها في الطرف الأمامي من القائمة المرتبطة الجديدة. لاحظ أن القائمة المرتبطة فارغة وهناك عقدة واحدة فقط. تعقيد الوقت هو o (n)
الطريقة 1: (اجتياز)
// الطريقة: انعكاس لقائمة المرتبطة العكسية العامة المرتبطة (رأس العقدة) {// إذا كانت القائمة المرتبطة فارغة أو لا يوجد سوى عقدة واحدة ، فلا يلزم انعكاس ، ويتم إرجاع عقدة الرأس المرتبطة الأصلية مباشرة إلى القائمة المرتبطة الأصلية (head == null || رأس القائمة المرتبطة الجديدة بعد الانعكاس! = null) {next = current.next ؛ العقدة التالية إلى عقدة الرأس في القائمة المرتبطة الجديدة = التيار ؛في الكود أعلاه ، الرمز الأساسي هو الأسطر 16 و 17.
الطريقة 2: (عودة)
هذه الطريقة صعبة بعض الشيء ، لذلك لن أتحدث عنها الآن.
7. طباعة قائمة واحدة مرتبطة من النهاية إلى النهاية:
لهذا النوع من الترتيب المقلوب ، يجب أن نفكر في Stack ، أولاً داخل وأول. لذلك ، يستخدم هذا السؤال إما المكدس بنفسك أو يتيح للنظام استخدام المكدس ، أي العودية. انتبه إلى الحالة التي تكون فيها القائمة المرتبطة فارغة. تعقيد الوقت هو o (n)
ملاحظة: لا تفكر في عكس القائمة المرتبطة المفردة أولاً ثم اجتياز الإخراج.
الطريقة 1: (إنشاء كومة جديدة بنفسك)
// الطريقة: طباعة قائمة واحدة مرتبطة من النهاية إلى النهاية العكسية (رأس العقدة) {if (head == null) {return ؛ إنشاء عقدة مكدس جديدة = الرأس. // اضغط على المكدس يطبع العقدة بينما (stack.size ()> 0) {system.out.println (stack.pop (). data) ؛الطريقة 2: (استخدم كومة النظام: رمز متكرر وأنيق وموجز)
public void reverseprint (head) {if (head == null) {return ؛الملخص: تعتمد الطريقة 2 على تنفيذ العوالم. يتم تنفيذ المكدس الصريح للطريقة 1 بناءً على الحلقات ، والرمز أكثر قوة.
8. تحديد ما إذا كانت القائمة المرتبطة واحدة لها حلقة:
يتم استخدام مؤشرتين أيضًا هنا.
لذلك ، نستخدم مؤشرين لتجارة: يأخذ المؤشر الأول خطوة واحدة في كل مرة ، والمؤشر الثاني يأخذ خطوتين في وقت واحد. التعقيد الوقت هو o (n).
طريقة:
// الطريقة: تحتوي القائمة المرتبطة على حلقة Boolean Hascycle (Node Head) {if (head == null) {return false ؛ ) {first. next ؛ عودة الحلقةرمز الإصدار الكامل: (بما في ذلك جزء الاختبار)
هنا ، نحتاج أيضًا إلى إضافة طريقة إضافة (عقدة العقدة) الزائدة ، والتي يجب استخدامها عند إنشاء قائمة مرتبطة دائرية أحادية الاتجاه.
LinkList.java: Head Public Class {Public Node Head ؛ ll) { / /إذا كانت عقدة الرأس فارغة ، فهذا يعني أنه لم يتم إنشاء القائمة المرتبطة بعد ، ثم قم بتعيين العقدة الجديدة إلى رأس العقدة الجديدة (Data) ؛ قم بإنشاء عقدة جديدة ، ضعها خلف العقدة الحالية (ربط العقدة الجديدة مع القائمة المرتبطة) Current.next = New Node (Data) ؛ ؛ ؛ العقدة) {if (node == null) {return ؛ الطريقة: قائمة مرتبطة واحدة تحتوي على حلقة منطقية (N ODE HEAD) {if (head == null) {return false ؛ أولا = next القائمة لها حلقة TRUE ؛ بيانات Int ؛ إضافة البيانات إلى (int i = 0 ؛ i <4 ؛ i ++) {list.add (i) ؛ هي حلقة في القائمة المرتبطة. ملاحظة: بنية الحلقة التي تم الحصول عليها في هذا الوقت هي بنية الشكل 1 في القسم التالي 8. System.out.println (list.hascycle (list.head)) ؛الرمز الذي يكتشف ما إذا كانت القائمة المرتبطة واحدة تحتوي على حلقة هي السطر 50.
السطر 88: نستمر في إضافة عقدة الرأس إلى القائمة المرتبطة ، وسيتم حلق القائمة المرتبطة الفردية في هذا الوقت. تأثير التشغيل النهائي صحيح.
إذا تم حذف 88 سطرًا من التعليمات البرمجية ، فلن يكون القائمة المرتبطة المفردة حلقات في هذا الوقت ، وتأثير التشغيل خاطئ.
9. أخرج القائمة المرتبطة بالحلقة ، طول الحلقة:
قائمة الارتباطات التي نواجهها عادة ما يلي: (الشكل 1)
طول الحلقة في الصورة أعلاه هو 4.
ولكن من الممكن أن يكون ما يلي أيضًا: (الشكل 2)
في هذا الوقت ، طول الحلقة في الصورة أعلاه هو 3.
فكيف تجد طول الحلقة؟
فكرة:
هنا ، نحتاج أولاً إلى استخدام طريقة hascycle في القسم 7 أعلاه (الطريقة لتحديد ما إذا كانت هناك حلقة في القائمة المرتبطة). إنها تُرجع القيمة للعقدة حيث نلتقي. بعد ذلك ، يمكننا الحصول على العقدة حيث نلتقي.
طريقة:
// الطريقة: تحديد ما إذا كانت القائمة المرتبطة واحدة لها حلقة. العقدة التي تم إرجاعها هي العقدة التي تلتقي بها. . فارغة ؛ تمثل عقدة المعلمة العقدة حيث تلبي GetCyCleLengle (Node) {if (head == null) {return 0 ؛ Current.Next ؛رمز الإصدار الكامل: (بما في ذلك جزء الاختبار)
LinkList Public Linklist {Public Node Head العقدة فارغة ، فهذا يعني أن القائمة المرتبطة لم يتم إنشاؤها بعد ، ثم قم بتعيين العقدة الجديدة إلى رأس العقدة (Data) ؛ العقدة الحالية (ربط العقدة الجديدة مع القائمة المرتبطة. تشير العقدة الحالية إلى العقدة المضافة حديثًا} // الأسلوب الزائد: إضافة عقدة إلى القائمة المرتبطة الفراغ العام إضافة (عقدة العقدة) {if (node == null) {return ؛ {Head = Current ؛ من Node Public Void Print (Node Node) {if (node == null) {return ؛ Current.Next ؛ أولا = العقدة ؛ القائمة المرتبطة هي عودة تشبه الحلقة أولاً ؛ تمثل عقدة المعلمة العقدة حيث تلبي GetCyCleLengle (Node) {if (head == null) {return 0 ؛ Current.NEX خاصة ، لأن أذونات الخاصة لا يمكن الوصول إليها إلا في هذه الفئة. بيانات Int ؛ = NULL ؛ ؛ العملية هي بنية الشكل 2 في هذا القسم Current = list1.hascycle (list1.head) ؛ ) ؛تأثير الجري:
إذا تم تغيير رمز الاختبار أعلاه للخطوط 104 إلى 122 إلى ما يلي: (أي ، قم بتغيير الهيكل في الشكل 2 إلى الهيكل في الشكل 1)
static void main (string [] args) {LinkList List1 = New LinkList () ؛ (List1.Head) ؛ ملاحظة: بنية هذه الحلقة التي تم الحصول عليها في هذا الوقت هي بنية الشكل 1 في هذا القسم. Node Current = list1.hascycle (list1.head) ؛نتائج التشغيل:
إذا قمت بحذف السطر الثامن في الكود أعلاه ، فلا تحتوي القائمة المرتبطة على حلقات ، وبالتالي فإن نتيجة التشغيل هي 0.
10. في القائمة المرتبطة الفردية ، نقطة انطلاق الحلقة المستخرجة:
قائمة الارتباطات التي نواجهها عادة ما يلي: (الشكل 1)
نقطة البداية 1 من الحلقة في الصورة أعلاه.
ولكن من الممكن أن يكون ما يلي أيضًا: (الشكل 2)
في هذا الوقت ، تكون نقطة انطلاق الحلقة في الصورة أعلاه 2.
الطريقة 1:
نحتاج هنا إلى استخدام طريقة إخراج طول الحلقة في القسم 8 أعلاه إلى GetCyCleLength ، واستخدام هذه الطريقة للحصول على طول الحلقة. بعد الحصول على طول الحلقة ، يجب استخدام متغيرات المؤشر أولاً. لقاء ، عقدة عندما يجتمعون.
ملاحظة: من أجل العثور على نقطة انطلاق الحلقة ، نحتاج أولاً إلى الحصول على طول الحلقة ، ومن أجل الحصول على طول الحلقة ، نحتاج أولاً إلى تحديد ما إذا كانت هناك حلقة. لذلك هناك بالفعل ثلاث طرق تستخدم هنا.
تنفيذ الكود:
الكود الأساسي للطريقة 1:
// الطريقة: احصل على نقطة بداية الحلقة. يمثل طول المعلمة طول الحلقة العامة GetCyclestart (رأس العقدة ، int cyclelength) {if (head == null) {return null ؛ إلى خطوة الطول (int i = 0 ؛ i <cyclelength ؛ i ++) {second = second.next ؛ ! = NULL) {first. next ؛ عودة لاغية ؛رمز الإصدار الكامل: (بما في ذلك جزء الاختبار)
LinkList Public Linklist {Public Node Head العقدة فارغة ، فهذا يعني أن القائمة المرتبطة لم يتم إنشاؤها بعد ، ثم قم بتعيين العقدة الجديدة إلى رأس العقدة (Data) ؛ العقدة الحالية (ربط العقدة الجديدة مع القائمة المرتبطة. تشير العقدة الحالية إلى العقدة المضافة حديثًا} // الأسلوب الزائد: إضافة عقدة إلى القائمة المرتبطة الفراغ العام إضافة (عقدة العقدة) {if (node == null) {return ؛ {Head = Current ؛ من Node Public Void Print (Node Node) {if (node == null) {return ؛ Current.Next ؛ أولا = العقدة ؛ القائمة المرتبطة هي عودة تشبه الحلقة أولاً ؛ تمثل عقدة المعلمة العقدة حيث تلبي GetCyCleLengle (Node) {if (head == null) {return 0 ؛ Current.Next ؛ يمثل طول المعلمة طول الحلقة العامة GetCyclestart (رأس العقدة ، int cyclelength) {if (head == null) {return null ؛ إلى خطوة الطول (int i = 0 ؛ i <cyclelength ؛ i ++) {second = second.next ؛ ! = NULL) {first. next ؛ إرجاع NULL ؛ بيانات Int ؛ = NULL ؛ ؛ الوقت هو بنية الشكل 2 في هذا القسم الحالي = list1.hascycle (List1.head) ؛ .out.println ("نقطة بداية الحلقة" + list1.getCyClestart (list1.head ، length) .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链表的经典面试题目，希望可以帮助大家顺利通过面试。