亲宝软件园·资讯

展开

Java 链表

明天一定. 人气:0

题目一

链表题——链表合并

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

具体题目如下

解法

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

加载全部内容

相关教程
猜你喜欢
用户评论