[数据结构与算法]LeetCood

【138】、复制带随机指针的链表

public Node copyRandomList(Node head) {
        if (head==null){
            return null;
        }
        //1)复制原有链表并插入
        Node cur=head;
        while (cur!=null){
            Node newNode=new Node(cur.val);
            newNode.next=cur.next;
            cur.next=newNode;
            cur=cur.next.next;
        }
        //2)完成对random的复制，映射关系已经保存到当前的链表中了
        cur=head;
        while (cur!=null){
            Node oldRandom=cur.random;
            Node newNode=cur.next;
            if (oldRandom==null){
                newNode.random=null;
            }else {
                newNode.random=oldRandom.next;
            }
            cur=cur.next.next;
        }
        //3)分开链表
        cur=head;
        Node newhead=cur.next;
        while (cur!=null){
            Node newNode=cur.next;
            cur.next=cur.next.next;
            if (newNode.next==null){
                break;
            }
            newNode.next=newNode.next.next;
            cur=cur.next;
        }
        return newhead;
    }

【1669】、合并两个链表

public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
            ListNode cur=list2;
            ListNode last2=null;
            while (cur.next!=null){
                cur=cur.next;
            }
            last2=cur;
            cur=list1;
            for (int i=0;i<b;i++){
                cur=cur.next;
            }
            last2.next=cur.next;
            cur=list1;
            for (int i=0;i<a-1;i++){
                cur=cur.next;
            }
            cur.next=list2;
            return list1;
    }

【725】、分割链表

public ListNode[] splitListToParts(ListNode head, int k) {
        if (head==null){
            return new ListNode[k];
        }
        ListNode[] ans=new ListNode[k];
        int len=0;
        ListNode cur=head;
        while (cur!=null){
            cur=cur.next;
            len++;
        }
        int remainder=len%k;
        int num=len/k;
        int index=0;
        ListNode newhead=head;
        cur=head;
        while (index<remainder){
            cur=newhead;
            for (int i=0;i<num;i++){
                cur=cur.next;
            }
            ans[index]=newhead;
            newhead=cur.next;
            cur.next=null;
            index++;
        }
        while (index<k){
            cur=newhead;
            for (int i=0;i<num-1;i++){
                cur=cur.next;
            }
            if (cur!=null){
                ans[index]=newhead;
                newhead=cur.next;
                cur.next=null;
            }
            index++;
        }
        return ans;
    }