快捷導(dǎo)航

java鏈表的常見簡(jiǎn)單面試算法題詳解

更新時(shí)間：2025年01月07日 09:24:07 作者：石以砥焉，以銳為利

文章總結(jié)：本文主要介紹了單鏈表的基本操作,包括頭插法、尾插法、鏈表翻轉(zhuǎn)、鏈表成環(huán)判斷、成環(huán)位置判斷、成環(huán)長度判斷,以及有序鏈表的合并,通過實(shí)例和代碼示例,詳細(xì)講解了每種操作的原理和實(shí)現(xiàn)方法

java鏈表的常見面試算法題

頭插法、尾插法

頭插法：先待插入指向頭結(jié)點(diǎn)的next，后頭結(jié)點(diǎn)的next指向待插入。

尾插法：借助尾指針，直接插入

 /**
     * 頭插法
     * @param head
     * @return
     */
    public static Node head_insert(Node head, int t){
        Node node=new Node(t);
        node.setNext(head.getNext());
        head.setNext(node);
        return head;
    }

    /**
     * 尾插法
     * @param head
     * @return
     */
    public static Node tail_insert(Node head,int t){
        Node tail=head;
        Node target=new Node(t);
        while (tail.getNext()!=null){
            tail=tail.getNext();
        }
        tail.setNext(target);
     return head;
    }
}

單鏈表翻轉(zhuǎn)

力扣：LCR 024. 反轉(zhuǎn)鏈表

將翻轉(zhuǎn)前的鏈表記pre，翻轉(zhuǎn)后的記next（也是head）。結(jié)點(diǎn)依次翻轉(zhuǎn)。

class Solution {
    public ListNode reverseList(ListNode head) {
     ListNode pre=null;ListNode next=null;
     while (head!=null){
         next=head.next;
         head.next=pre;
         pre=head;
         head=next;
     }
     return pre;
    }
}

鏈表成環(huán)判斷

力扣：141. 環(huán)形鏈表

定義兩個(gè)指針slow、fast，slow走一步，fast走兩步遍歷鏈表。相遇就有環(huán)

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
              return true;
            }
        }
        return false;

    }
}

鏈表成環(huán)位置判斷

力扣：LCR 022. 環(huán)形鏈表 II

（1）定義一個(gè)A指針（指向開始點(diǎn)A）、B指針（指向相遇點(diǎn)B）。以相同速度移動(dòng)，相遇點(diǎn)就是環(huán)的入口。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Boolean result=false;
        ListNode slow=head;
        ListNode fast=head;
        while (slow!=null&&fast!=null&&fast.next!=null){
           slow=slow.next;
           fast=fast.next.next;
           if(slow==fast){
               result=true;
               break;
           }
        }
        if(result==false){
         return null;
        }
        slow=head;
        while (slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
    }
}

（2）為什么慢指針和快指針相遇時(shí)一定沒走完一圈？

將環(huán)平鋪展開，假設(shè)慢指針走完一圈了，快指針走兩圈的距離。在下圖中看出快指針已經(jīng)超過了慢指針，中途一定有相遇的瞬間。

鏈表成環(huán)長度判斷

在上一題找到環(huán)入口的前提下，再定義一個(gè)指針，繞一圈環(huán)并記數(shù)。

有序鏈表的合并

力扣：21. 合并兩個(gè)有序鏈表

定義一個(gè)pre指針，始終指向已經(jīng)排好序的鏈表尾結(jié)點(diǎn)。定義一個(gè)虛擬節(jié)點(diǎn)作為pre的初始節(jié)點(diǎn)。

依次遍歷兩個(gè)鏈表取出小的那個(gè)結(jié)點(diǎn)作為pre的下一個(gè)結(jié)點(diǎn)。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
     ListNode head=new ListNode(0);
     ListNode pre=head;
     while(list1!=null&&list2!=null){
        if(list1.val<list2.val){
          pre.next=list1;
          pre=list1;
          list1=list1.next;
        }else{
          pre.next=list2;
          pre=list2;
          list2=list2.next;
        }
     }
     if(list1==null){
     pre.next=list2;
     }else{
        pre.next=list1;
     }
     return head.next;
   }
}