劍指Offer之Java算法習(xí)題精講鏈表專項(xiàng)訓(xùn)練

更新時間：2022年03月22日 11:03:45 作者：明天一定.

跟著思路走，之后從簡單題入手，反復(fù)去看，做過之后可能會忘記，之后再做一次，記不住就反復(fù)做，反復(fù)尋求思路和規(guī)律，慢慢積累就會發(fā)現(xiàn)質(zhì)的變化

題目一

鏈表題——鏈表合并

根據(jù)給定的兩個升序鏈表合并為一個新的升序鏈表

具體題目如下

解法

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode a = new ListNode(0),b = a;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                a.next = list1;
                list1 = list1.next;
            }else{
                a.next = list2;
                list2 = list2.next;
            }
            a = a.next;
        }
        if(list1==null){
            a.next = list2;
        }
        if(list2==null){
            a.next = list1;
        }
        return b.next;
    }
}

?題目二

鏈表題——查找鏈表

根據(jù)給定的鏈表頭文件判斷其中是否有環(huán)

具體題目如下

?解法一

/**
 * 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) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        while(head!=null){
            if(!set.add(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

解法二

/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null){
            if(fast.next==null) return false;
            slow = slow.next;
            fast = fast.next.next;
            if(fast==slow) return true;
        }
        return false;
    }
}

題目三

鏈表題——查找數(shù)組中元素位置

根據(jù)給定的鏈表頭節(jié)點(diǎn)查找返回鏈表入環(huán)的第一個節(jié)點(diǎn)

具體題目如下

?解法一

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        while(head!=null){
            if(!set.add(head)){
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }
}

解法二

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

題目四

鏈表題——查找鏈表相交起始節(jié)點(diǎn)

根據(jù)給定的兩個鏈表頭節(jié)點(diǎn)按照指定條件查找起始節(jié)點(diǎn)

具體題目如下

解法一

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<ListNode>();
        while(headA!=null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB!=null){
            if(!set.add(headB)){
                return headB;
            }
            set.add(headB);
            headB = headB.next;
        }
        return null;
    }
}

解法二

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while(a != b){
            if(a == null) a = headB;
            else a = a.next;
            if(b == null) b = headA;
            else b = b.next;
        }
        return a;
    }
}

題目五

鏈表題——鏈表操作

根據(jù)給定的鏈表刪除指定節(jié)點(diǎn)并返回頭節(jié)點(diǎn)

具體題目如下

?解法

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode(-1);
        node.next = head;
        ListNode x = findFromEnd(node,n+1);
        x.next = x.next.next;
        return node.next;
    }
    private ListNode findFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0;i<k;i++){
            fast = fast.next;
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

題目六

鏈表題——查找鏈表中間節(jié)點(diǎn)

根據(jù)給定的鏈表頭節(jié)點(diǎn)查找其中間節(jié)點(diǎn)

具體題目如下

?解法

/**
 * 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) {
        ListNode fast = head ;
        ListNode slow = head ;
        while(fast!=null){
            if(fast.next == null) return slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

到此這篇關(guān)于劍指Offer之Java算法習(xí)題精講鏈表專項(xiàng)訓(xùn)練的文章就介紹到這了,更多相關(guān)Java 鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: