剑指Offer之Java算法习题精讲链表专项训练

题目一

链表题——链表合并

根据给定的两个升序链表合并为一个新的升序链表

具体题目如下

解法

/**
 * 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;
    }
}

 题目二

链表题——查找链表

根据给定的链表头文件判断其中是否有环

具体题目如下

 解法一

/**
 * 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;
    }
}

题目三

链表题——查找数组中元素位置

根据给定的链表头节点查找返回链表入环的第一个节点

具体题目如下

 解法一

/**
 * 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;
    }
}

题目四

链表题——查找链表相交起始节点

根据给定的两个链表头节点按照指定条件查找起始节点

具体题目如下

解法一

/**
 * 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;
    }
}

题目五

链表题——链表操作

根据给定的链表删除指定节点并返回头节点

具体题目如下

 解法

/**
 * 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;
    }
}

题目六

链表题——查找链表中间节点

根据给定的链表头节点查找其中间节点

具体题目如下

 解法

/**
 * 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;
    }
}

到此这篇关于剑指Offer之Java算法习题精讲链表专项训练的文章就介绍到这了,更多相关Java 链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！