天天看點
傳回

連結清單相關面試題

連結清單相關面試題
public class Code01_LinkedListMid {
    public static void main(String[] args) {

    }

    public static class Node{
        public int value;
        public Node next;

        public Node(int v){
            this.value = v;
        }
    }

    // 1 2 3 4 5  傳回中點或上中點
    public static Node midOrUpMidNode(Node head){
        if(null == head || head.next == null || head.next.next==null){
            return head;
        }

        // 連結清單有3個點或以上
        Node slow = head.next;
        Node fast = head.next.next;
        while(null != fast.next && null != fast.next.next){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 1 2 3 4 5  傳回中點或下中點
    public static Node midOrDownMidNode(Node head){
        if(null == head || head.next == null){
            return head;
        }

        Node slow = head.next;
        Node fast = head.next;
        while(null != fast.next && null != fast.next.next){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // (中點或上中點)的前一個 1 2 3 4 5
    public static Node midOrUpMidPreNode(Node head){
        if(null == head || head.next == null || head.next.next==null){
            return null;
        }

        Node slow = head;
        Node fast = head.next.next;
        while(null != fast.next && null != fast.next.next){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // (中點或下中點)的前一個 1 2 3 4 5
    public static Node midOrDownMidPreNode(Node head){
        if(null == head || head.next == null){
            return null;
        }

        if(head.next.next == null){
            return head;
        }

        Node slow = head;
        Node fast = head.next;
        while(null != fast.next && null != fast.next.next){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

判斷一個連結清單是否是回文結構

public class IsPalindromeTest {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(2);
        Node n5 = new Node(1);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        System.out.println(isPalindrome(n1));
    }

    public static class Node{
        private int value;
        private Node next;
        public Node(int value){
            this.value = value;
        }
    }

    public static boolean isPalindrome(Node head){
        if(null == head || head.next == null){
            return true;
        }

        Node n1 = head;
        Node n2 = head;

        while(n2.next != null && n2.next.next != null){
            n1 = n1.next;
            n2 = n2.next.next;
        }

        n2 = n1.next;
        n1.next = null;
        Node n3 = null;
        // 逆序連結清單
        while(n2 != null){
            n3 = n2.next; // save next node
            n2.next = n1; // next of right node convert
            n1 = n2; // n1 move
            n2 = n3; // n2 move
        }

        n3 = n1; // save last node 最後一個節點
        n2 = head; // 左邊第一個節點
        boolean res = true;
        while(n2 != null && n1 != null){
            if(n2.value != n1.value){
                res = false;
                break;
            }
            n1 = n1.next;
            n2 = n2.next;
        }

        // 将逆序的連結清單再還原回來
        n1 = n3.next;
        n3.next = null;
        while(n1 != null){
            n2 = n1.next;
            n1.next = n3;
            n3 = n1;
            n1 = n2;
        }

        return res;
    }
}

給出一個連結清單,小于某個數的放在連結清單左邊,等于某個數的放在連結清單中間,大于某個數的放在連結清單右邊

public class SmallEqualsBigger {
    public static void main(String[] args) {
        Node n1 = new Node(5);
        Node n2 = new Node(3);
        Node n3 = new Node(3);
        Node n4 = new Node(2);
        Node n5 = new Node(1);
        Node n6 = new Node(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;

        n1 = listPartition2(n1,3);
        while(n1 != null){
            System.out.print(n1.value+ "  ");
            n1 = n1.next;
        }
    }

    public static class Node{
        private int value;
        private Node next;
        public Node(int value){
            this.value = value;
        }
    }

    // 方法一
    public static Node listPartition1(Node head, int pivot){
        if(head == null){
            return head;
        }

        Node cur = head;
        int i = 0;
        while(cur != null){
            i++;  // 計算對外連結表節點的總個數
            cur = cur.next;
        }

        Node[] nodeArr = new Node[i];
        i = 0;
        cur = head;
        // 把連結清單放到數組中
        for (i = 0; i < nodeArr.length; i++) {
            nodeArr[i] = cur;
            cur = cur.next;
        }

        arrPartition(nodeArr, pivot);
        for (i = 1; i != nodeArr.length; i++) {
            nodeArr[i-1].next = nodeArr[i];
        }

        nodeArr[i-1].next = null; // 最後一個節點
        return nodeArr[0];// 傳回新的頭節點
    }

    public static void arrPartition(Node[] nodeArr, int pivot){
        int small = -1;
        int big = nodeArr.length;
        int index = 0;
        while(index<big){
            if(nodeArr[index].value < pivot){
                swap(nodeArr,index++,++small);
            }else if(nodeArr[index].value == pivot){
                index++;
            }else if(nodeArr[index].value > pivot){
                swap(nodeArr,index,--big);
            }
        }
    }

    public static void swap(Node[] nodeArr, int node1, int node2){
        Node temp = nodeArr[node1];
        nodeArr[node1] = nodeArr[node2];
        nodeArr[node2] = temp;
    }

    // 方法二
    public static Node listPartition2(Node head, int pivot){
        // 使用6個變量
        Node sH = null;  // small head
        Node sT = null;  // small tail
        Node eH = null;  // equal head
        Node eT = null;  // equal tail
        Node bH = null;  // big head
        Node bT = null;  // big tail
        Node next = null; // save next node

        while(head != null){
            next = head.next;
            head.next = null;

            if(head.value < pivot){
                if(sH == null){
                    sH = head;
                    sT = head;
                }else{
                    sT.next = head;
                    sT = head;
                }
            }else if(head.value == pivot){
                if(eH == null){
                    eH = head;
                    eT = head;
                }else{
                    eT.next = head;
                    eT = head;
                }
            }else {
                if(bH == null){
                    bH = head;
                    bT = head;
                }else{
                    bT.next = head;
                    bT = head;
                }
            }

            head = next;
        }

        if(sT != null){
            sT.next = eH;
            eT = eT == null ? sT : eT; // 下一步,誰去連大于區域的頭,誰就變成eT
        }

        if(eT != null){
            eT.next = bH;
        }

        sH = sH == null ? (eH == null ? bH: eH): sH;
        return sH;
    }
}           
public class Code02_CopyListWithRand {
    public static void main(String[] args) {
        Node n1 = new Node(5);
        Node n2 = new Node(4);
        Node n3 = new Node(3);
        Node n4 = new Node(2);
        Node n5 = new Node(1);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        Node newN1 = copyListWithRand2(n1);
        while(null != newN1){
            System.out.print(newN1.value+" ");
            newN1 = newN1.next;
        }
    }

    public static class Node{
        public int value;
        public Node next;
        public Node random;

        public Node(int value){
            this.value = value;
        }
    }

    public static Node copyListWithRand2(Node head){
        if(null == head){
            return null;
        }

        Node cur = head;
        Node next = null;

        // 1 -> 2
        // 1 -> 1' -> 2
        while(null != cur){
            next = cur.next;
            // 新生成的節點,插入到原來節點後面
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }

        cur = head;
        Node curCopy = null;
        // 1 -> 1' -> 2 -> 2'
        while(null != cur){
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.random = (cur.random == null ? null : cur.random.next);
            cur = next;
        }

        Node res = head.next;
        cur = head;
        while(cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = (null != next ? next.next : null);
            cur = next;
//            cur.next = cur.next.next;
//            cur = cur.next;
        }

        return res;
    }
}
連結清單 i++ 逆序 數組 幹貨
上一篇: 連結清單常見面試題
下一篇: Windows server 2003

繼續閱讀