Java鍊錶實例分析

1、刪除值為val的所有節點

刪除鍊錶中等於給定值val的所有節點。 【OJ連結】

定義兩個指標prev、cur，cur指向頭節點的下一個節點，prev總是指向cur的前一個結點（方便刪除節點）。透過cur指標去遍歷鍊錶，和val值比較，相同就刪除這個節點。最後再來比較頭節點。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }
}

2、反轉鍊錶

反轉一個鍊錶。 【OJ連結】

在遍歷鍊錶時，將目前節點的 指標改為指向前一個節點。由於節點沒有引用其前一個節點，因此必須事先儲存其前一個節點。在更改引用之前，還需要儲存後一個節點。最後返回新的頭引用。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
}

3、返回鍊錶中間節點

給定一個帶有頭節點的非空單鍊錶，傳回鍊錶的中間節點。如果有兩個中間節點，則傳回第二個中間節點。 【OJ連結】

我們可以定義兩個快慢指標（fast、slow），都指向頭節點。快指針每次走兩步，慢指針每次走一步。鍊錶有偶數個節點時，fast=null時slow為中間節點；鍊錶有奇數個節點時，fast.next=null時slow為中間節點。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

4、傳回鍊錶第K個節點

#輸入一個鍊錶，回傳該鍊錶中倒數第K個節點。 【OJ連結】

這個題和找中間節點的想法相似。定義兩個指標（fast、slow）。在K合理的前提下，我們可以讓快指標先走K-1步，然後快慢指標同時向後走，當fast到達鍊錶結尾時，slow就指向倒數第K個節點。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1>0){
            if(fast.next==null){
                return null;
            }
            fast=fast.next;
            //先让快节点走k-1步
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
       
    }
}

5、合併有序鍊錶

將兩個有序鍊錶合併為一個有序鍊錶並傳回。新鍊錶是透過拼接給定的兩個鍊錶的所有節點組成的。 【OJ連結】

解這個題，需要定義假節點來充當新鍊錶的頭節點。透過兩個鍊錶的頭節點去遍歷兩個節點，去比較兩個鍊錶對應節點的值，將值小的節點連接到新鍊錶的後面，知道兩個鍊錶遍歷完，當其中一個鍊錶為空時，直接將另一個鍊錶連接到新鍊錶後面即可。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //创建虚拟节点，充当新链表的头节点，值不代表任何意义
        ListNode node=new ListNode(-1);
        ListNode cur=node;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1==null){
            cur.next=list2;
        }else{
            cur.next=list1;
        }
        return node.next;
    }
}

6、以值分割鍊錶

將一個鍊錶依照給定值X分成兩個部分，所有小於X的節點排在大於或等於X的節點之前。不改變節點原來的順序。 【OJ連結】

首先我們需要定義四個指標（bs、be、as、ae）分別表示小於X部分鍊錶的頭節點和尾節點、大於X部分鍊錶的頭節點和尾節點。透過頭節點遍歷鍊錶，將鍊錶分為兩部分。最後將兩個鍊錶連接起來即可。需要特別注意，當小於X部分鍊錶不為空時，我們需要手動將ae.next置為空。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=cur;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
            //如果小于X部分为空，则直接返回大于X部分即可。此时ae.next一定为null
        }
        be.next=as;//否则连接小于X和大于X部分
        if(as!=null){
           ae.next=null;
           //当小于X部分不为空时，ae.next可能不为null，需要手动置为null
        }
        return bs;
    }
}

7、判讀回文鍊錶

#判斷鍊錶是不是回文鍊錶。 【OJ連結】

首先我們需要找到鍊錶的中間節點，然後將後半段鍊錶反轉。最後透過兩邊逐步比較即可。特別注意，當鍊錶結點個數為偶數時，因為中間節點的緣故，兩邊遍歷時，無法相遇，需要特殊處理。

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return false;
        }
        if(A.next==null){
            return true;
        }
        //求链表的中间节点
        ListNode slow=A;
        ListNode fast=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转后半段链表
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //判断回文链表
        while(slow!=A){
            if(slow.val!=A.val){
              return false;
           }
            if(A.next==slow){
                return true;
            }
            slow=slow.next;
            A=A.next;
        }
        return true;
    }
}

8、找兩個鍊錶的公共節點

輸入兩個鍊錶，輸出兩個鍊錶的第一個公共節點。沒有回傳NULL。 【OJ連結】

兩個鍊錶相交呈現Y字型。那麼兩個鍊錶長度的差肯定是未相交前兩個鍊錶節點的差。我們需要求出兩個鍊錶的長度。定義兩個指標（pl、ps），讓pl指向長的鍊錶，ps指向短的鍊錶。求兩個鍊錶的長度差len。讓pl想走len步。這樣兩個鍊錶的剩餘長度就相同。此時兩個指標同時遍歷連個鍊錶，如果其指向一致，則兩個鍊錶相交，否則，兩個鍊錶不相交。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //求链表长度
    public int len(ListNode head){
        int len=0;
        while(head!=null){
            head=head.next;
            len++;
        }
        return len;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pl=headA;
        ListNode ps=headB;
        int lenA=len(headA);
        int lenB=len(headB);
        int len=lenA-lenB;
        if(len<0){
            //pl指向长的链表，ps指向短的链表
            pl=headB;
            ps=headA;
            len=-len;
        }
        while(len--!=0){
            pl=pl.next;
        }
        while(pl!=null){
            if(pl==ps){
                return pl;
            }
            pl=pl.next;
            ps=ps.next;
        }
        return null;
    }
}

9、判斷成環鍊錶

判斷鍊錶中是否有環。 【OJ連結】

還是快慢指標。慢指針一次走一步，快指針一次走兩步。兩個指標從鍊錶起始位置開始運作。如果鍊錶帶環則一定會在環中相遇，否則快指針率先走到鍊錶的末端。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;//链表为空或者只有一个节点时，没有环
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
                //如果快慢节点可以相遇，表示链表有环
            }
        }
        return false;
    }
}

10、返回成環鍊錶的入口

給定一個鍊錶，判斷鍊錶是否有環並回傳入環的節點。如果沒有環，則回傳NULL。 【OJ連結】

让一个指针从链表的其实在位置开始遍历，同时另一个指针从上题中两只真相与的位置开始走，两个指针再次相遇时的位置肯定为环的入口

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //判断链表是否有环，并返回第一次快慢节点相交的位置
    public ListNode hasCycle(ListNode head){
         if(head==null||head.next==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
               return slow;
            }
        }
        return null;
    }
    //当返回的结点与头节点再次相交时，为环的入口
    public ListNode detectCycle(ListNode head) {
        ListNode node=hasCycle(head);
        if(node==null){
            return null;
        }else{
            while(head!=node){
                head=head.next;
                node=node.next;
            }
        }
        return head;
    }
}

以上是Java鍊錶實例分析的詳細內容。更多資訊請關注PHP中文網其他相關文章！