链表问题

本篇文章列举常见的链表相关问题

leetcode160 相交链表

/**
 * 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 curA = headA;
        ListNode curB = headB;
        while(curA!= curB){
            if(curA!=null){
                curA = curA.next;
            }else{
                curA = headB;
            }

            if(curB!=null){
                curB = curB.next;
            }else{
                curB = headA;
            }
        }

        return curA;

    }
}

这个题比较简单，思路就是把A和B合成一条链表，遍历即可

leetcode138 随机链表的复制

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur!=null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while(cur!=null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

这题是HashMap的妙用

leetcode25 K个一组翻转链表

/**
 * 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 reverseKGroup(ListNode head, int k) {

        ListNode cur=head;
        for(int i=0;i<k;i++){
            if(cur==null){
                return head;
            }
            cur=cur.next;
        }

        ListNode newhead=reverseK(head,cur);
        head.next=reverseKGroup(cur,k);

        return newhead;

    }

    //长度为K的链表反转
    public ListNode reverseK(ListNode head,ListNode end){

        ListNode pre=null;
        ListNode cur=head;
        while(cur!=end){
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }

        return pre;

    }
}

这题就是链表反转基础代码结合递归

leetcode23 合并K个升序链表

/**
 * 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 mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<>((o1,o2)->o1.val-o2.val);
        for(ListNode node:lists){
            while(node!=null){
                q.offer(node);
                node = node.next;
            }
        }

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(!q.isEmpty()){
            cur.next = q.poll();
            cur = cur.next;
            if(q.isEmpty()){
                cur.next = null;
            }
        }

        return dummy.next;
    }
}

这题是优先队列(PriorityQueue)的妙用