(転載)一枚の文章は面接中のリンクテーマを解決します.(java実現)

一つの文章は面接中のリンクテーマを解決します.(java実現)から始まります.
最近はデータ構造とアルゴリズムの問題をまとめました.これは第二篇の文章で、チェーンについての第一篇の文章は二叉樹についての無駄話を参照してください.

class ListNode {
    ListNode next;
    int val;
    ListNode(int x){
        val = x;
        next = null;
    }
}

1.反転チェーン

ListNode reverse(ListNode node){
        ListNode prev = null;
        while(node!=null){
            ListNode tmp = node.next;
            node.next = prev;
            prev = node;
            node = tmp;
        }
        return prev;
    }
    //    (    )
    ListNode reverse2(ListNode head){
        if(head.next == null){
            return head;
        }
        ListNode reverseNode = reverse2(head.next);
        head.next.next = head;
        head.next = null;
        return reverseNode;

    }

2.チェーンテーブルにリングがあるかどうかを判断する

    boolean hasCycle(ListNode head){
        if(head == null|| head.next == null){
            return false;
        }
        ListNode slow,fast;
        fast = head.next;
        slow = head;
        while(fast!=slow){
            if(fast==null||fast.next==null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

3、チェーンの並べ替え

    ListNode sortList(ListNode head){
        if(head == null|| head.next == null){
            return head;
        }
        ListNode mid = middleNode(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
        return merge(left, right);
    }
    ListNode middleNode(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    ListNode merge(ListNode n1,ListNode n2){
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        while (n1!=null&&n2!=null) {
            if(n1.val

4.チェーン表の加算加算と加算

    ListNode addLists(ListNode l1,ListNode l2){
        if(l1==null&&l2==null){
            return null;
        }
        ListNode head = new ListNode();
        ListNode point = head;
        int carry = 0;
        while(l1!=null&&l2!=null){
            int sum = carry + l1.val + l2.val;
            point.next = new ListNode(sum%10);
            carry = sum/10;
            l1 = l1.next;
            l2 = l2.next;
            point = point.next;
        }
        while(l1!=null){
            int sum = carry + l1.val;
            point.next = new ListNode(sum%10);
            carry = sum/10;
            l1 = l1.next;
            point = point.next;
        }
        while(l2!=null){
            int sum = carry + l2.val;
            point.next = new ListNode(sum%10);
            carry = sum/10;
            l2 = l2.next;
            point = point.next;
        }
        if(carry!=0){
            point.next = new ListNode(carry);

        }
        return head.next;
    }

5.チェーンテーブルの最後からn番目のノードを得る

    ListNode nthToLast(ListNode head,int n ){
        if(head == null||n<1){
            return null;
        }
        ListNode l1 = head;
        ListNode l2 = head;
        for(int i = 0;i

6.チェーンテーブルの最後からn番目のノードを削除する

    ListNode deletenthNode(ListNode head,int n){
        // write your code here
        if (n <= 0) {
            return null;
        }

        ListNode dumy = new ListNode(0);
        dumy.next = head;
        ListNode prdDel = dumy;
        for(int i = 0;i

7.チェーンの重複要素を削除する

    ListNode deleteMuNode(ListNode head){
        if(head == null){
            return null;
        }
        ListNode node = head;
        while(node.next != null){
            if(node.val == node.next.val){
                node.next = node.next.next;
            }else{
                node = node.next;
            }
        }
        return head;

    }

8.チェーンテーブルに重複する要素iiを削除し、重複するノードを削除する

    ListNode deleteMuNode2(ListNode head){
        if(head == null||head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while(head.next!=null&&head.next.next!=null){
            if(head.next.val == head.next.next.val){
                int val = head.next.val;
                while(head.next.val == val&&head.next != null){
                    head.next = head.next.next;
                }
            }else{
                head = head.next;
            }
        }
        return dummy.next;
    }

9.回転リスト

    ListNode rotateRight(ListNode head,int k){
        if(head ==null){
            return null;
        }
        int length = getLength(head);
        k = k % length;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        ListNode tail = dummy;
        for(int i = 0;i

10.チェーンの並べ替え

    ListNode reOrder(ListNode head){
        if(head == null||head.next == null){
            return;
        }
        ListNode mid = middleNode(head);
        ListNode tail = reverse(mid.next);
        mergeIndex(head, tail);
    }
    private void mergeIndex(ListNode head1,ListNode head2){
        int index = 0;
        ListNode dummy = new ListNode(0);
        while (head1!=null&&head2!=null) {
            if(index%2==0){
                dummy.next = head1;
                head1 = head1.next;
            }else{
                dummy.next = head2;
                head2 = head2.next;
            }
            dummy = dummy.next;
            index ++;
        }
        if(head1!=null){
            dummy.next = head1;
        }else{
            dummy.next = head2;
        }
    }

11.チェーンの区分

    ListNode partition(ListNode head,int x){
        if(head == null){
            return null;
        }
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        ListNode leftDummy = left;
        ListNode rightDummy = right;
        while(head!=null){
            if(head.val

12.チェーンのnからmの間のノードを反転させる

    ListNode reverseN2M(ListNode head,int m,int n){
        if(m>=n||head == null){
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        for(int i = 1;i

13.Kの並べ替えチェーンを結合する

    ListNode mergeKListNode(ArrayList k){
        if(k.size()==0){
            return null;
        }
        return mergeHelper(k,0,k.size()-1);
    }
    ListNode mergeHelper(List lists,int start,int end){
        if(start == end){
            return lists.get(start);
        }
        int mid = start + ( end - start )/2;
        ListNode left = mergeHelper(lists, start, mid);
        ListNode right = mergeHelper(lists, mid+1, end);
        return mergeTwoLists(left,right);
    }
    ListNode mergeTwoLists(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(list1!=null&&list2!=null){
            if(list1.val

作者:IOExceptionerリンク:https://www.jianshu.com/p/a64d1ef95980 出所:著作権は著者の所有になります.商業転載は作者に連絡して授権を獲得してください.商業転載ではないので、出典を明記してください.
終了