摘要：性質(zhì)相對(duì)于數(shù)組，長(zhǎng)度可變插入刪除更容易。為了正確的反轉(zhuǎn)一個(gè)鏈表，需要調(diào)整鏈表中指針的方向指針?lè)聪颉Ｗ⒁猓趩捂湵碇校瑢⒁粋€(gè)節(jié)點(diǎn)的指向后繼的指針指向它的前驅(qū)，將會(huì)導(dǎo)致鏈表的斷裂。

雖是讀書(shū)筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復(fù)制黨

以下是算法導(dǎo)論第十章的學(xué)習(xí)筆記

棧頂指針 top (初始值top = -1)指向棧頂元素，插入時(shí)先修改指針再插入，刪除時(shí)先取棧頂元素再修改指針.

后進(jìn)先出
入棧，出棧都是O(1)

javapublic class Stack {
    private int[] array = new int[5];
    private int top = -1;

    public Boolean stackempty(){
        if(top == -1){
            return true;
        }
        else 
            return false;
    }

    public void push(int x){
        if(top<=array.length-1){
            array[++top] = x;
        }
        else{
            System.out.println("overflow");
        }
    }

java    public int pop() {
        int number = -1;
        if(stackempty() != true){
            number = array[top];
            top--;
            return number;
        }
        else
        {
            System.out.println("underflow");
            return -1;
        }
    }

javapublic class Queue {
    private int[] array = new int[4];
    private int head = 1;
    private int tail = 1;
    //入隊(duì)
    public void enqueue(int x){
        //處理上溢
        try{
            if(head != tail +1){
                array[tail++] = x;
                if(tail == array.length){
                    tail = 0;
                }
            }
            else{
                System.out.println("overflow");
                throw new Exception("queue overflow");
            }
        }catch(Exception e){
            e.printStackTrace();
        }
    }

java    //出隊(duì)
    public int dequeue(){
        int number=0;
        try{
            if(tail != head){
                number = array[head];
                head++;
            }
            else{
                throw new Exception("queue underflow");
            }

        }catch(Exception e){
            System.out.println("underflow");
            e.printStackTrace();
        }
        return number;
    }

javapublic class LinkedList {
    private Node head;
    private Stack s;
    LinkedList(){
        head = null;
        s = new Stack();
    }
    private static class Node{
        int item;
        Node next;

        Node(){
            this.item = 0;
            this.next = null;
        }
        Node(int item, Node next){
            this.item = item;
            this.next = next;
        }
    }

    public void insert(int x){
        Node node = new  Node(x, null);
        Node p = head;
        // 注意鏈表為空的時(shí)候的插入
        if(head==null){
            head = node;
        }
        // 尾插法
        else{
            while(p.next != null){
                p = p.next;
            }
            p.next = node;
        }
    }
    public void travese(Node head){
        Node p = head;
        while(p!=null){
            System.out.println(p.item);
            p = p.next;
        }
    }

javapublic class DoubleLinkedList {
    // 哨兵節(jié)點(diǎn)nil(作為表頭指針)
    private Node nil;
    // 初始化一個(gè)鏈表
    DoubleLinkedList(){
        nil = new Node();
        nil.next = nil;
        nil.prev = nil;
        count = 0;
    }
    // 鏈表長(zhǎng)度
    private int count;
    private static class Node{
        int item;
        Node next;
        Node prev;

        Node(){
            item = 0;
            next = null;
            prev = null;
        }
        Node(int item, Node next, Node prev){
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }

    //返回當(dāng)前鏈表的長(zhǎng)度
    public int length(){
        return count;
    }

    //獲取value為k的節(jié)點(diǎn)
    public Node listsearch(int k){
        Node result = null;
        Node head = nil;
        while(head.next != nil){
            if(head.next.item == k){
                result = head.next;
                break;
            }
            else
                head = head.next;
        }
        return result;
    }

    //插入一個(gè)節(jié)點(diǎn)在隊(duì)首
    public void listinsert(Node node){
            node.next = nil.next;
            nil.next.prev = node;
            nil.next = node;
            node.prev = nil;
            count++;
    }
    //根據(jù)value刪除一個(gè)節(jié)點(diǎn)
    public Node listdelete(Node node){
        Node head = nil;
        Node nodetodelete;
        while(head.next!=nil){
            if(head.next.item == node.item){
                nodetodelete = head.next; //將要?jiǎng)h除的節(jié)點(diǎn)
                head.next = nodetodelete.next;
                nodetodelete.next.prev  = head;
                nodetodelete = null;

                count--;
            }
            else{
                head = head.next;
            }
        }
        return node;
    }
    //輸出鏈表
    public void traverse(){
        Node head = nil;
        while( head.next!= nil){
            System.out.println(head.next.item);
            head = head.next;
        }
    }

java    public void reveaseoutput(Node head){
        Node p = head;
        if(p==null){
            System.out.println("empty list");
        }
        while(p != null){
            s.push(p.item);
            p = p.next;
        }
        while(s.stackempty()!= true){
            int n = s.pop();
            System.out.println(n);
        }
    }

javapublic void deleteNode(Node head, Node pToDeleted){
        if(head!=null){
            //要?jiǎng)h除的是尾節(jié)點(diǎn)
            if(pToDeleted.next == null){
                //如果要?jiǎng)h除的是鏈表唯一的節(jié)點(diǎn)
                if(head.next==null){
                    head = null;
                    System.out.println(head);
                    pToDeleted = null;
                }
                else{
                    Node p = head;
                    while(p.next!=pToDeleted){
                        p = p.next;
                    }
                    p.next = null;
                    pToDeleted =null;
                }
            }
            //要?jiǎng)h除的不是尾節(jié)點(diǎn)，且節(jié)點(diǎn)數(shù)大于1
            else{
                pToDeleted.item = pToDeleted.next.item;
                pToDeleted.next = pToDeleted.next.next;
                pToDeleted = null;
            }

        }else{
            System.out.println("the linklist is empty");
        }
    }

java    //遍歷鏈表一次，刪除倒數(shù)第K個(gè)元素
    public Node FindKthToTail(Node head, int k){
        Node p=head;
        Node q = head;
        int i;
        if(head==null || k==0){
            return null;
        }
        for(i=0;i

4. 反轉(zhuǎn)鏈表

題目：定義一個(gè)函數(shù)，輸入鏈表頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)。

解法：借助三個(gè)指針，prev, p, next. 避免指針斷裂。

（ 為了正確的反轉(zhuǎn)一個(gè)鏈表，需要調(diào)整鏈表中指針的方向【指針?lè)聪颉俊Ｗ⒁猓趩捂湵碇校瑢⒁粋€(gè)節(jié)點(diǎn)的指向后繼的指針指向它的前驅(qū)，將會(huì)導(dǎo)致鏈表的斷裂。導(dǎo)致無(wú)法在單鏈表中遍歷它的后繼節(jié)點(diǎn)，因此，在調(diào)整某一節(jié)點(diǎn)的 next 指針時(shí)，需要首先將其的后繼節(jié)點(diǎn)保存下來(lái)。）


代碼：

java    public Node reverse(){
        Node p = head;
        try{
            if(p!=null){
                Node pnext = p.next;
                p.next = null;
                while(pnext!= null){
                    Node r = pnext.next;
                    pnext.next = p;
                    p = pnext;
                    pnext = r;
                }
                }else{
                throw new Exception("empty list");
                }
        }catch(Exception e){
            e.printStackTrace();
        }finally{
            return p;
        }
    }



5 合并鏈表

題目：輸入兩個(gè)增序的鏈表，合并這兩個(gè)鏈表并使新鏈表仍然增序。

解法：重點(diǎn)強(qiáng)調(diào)魯棒性：兩個(gè)鏈表一個(gè)或者兩個(gè)都是null,兩個(gè)鏈表只有一個(gè)節(jié)點(diǎn)。

代碼：

java    public Node merge(Node head1, Node head2){
        if(head1 == null) {
            return head2;
        }
        if(head2 == null){
            return head1;
        }
        else{
            Node newhead;
            Node r;
            Node p = head1;
            Node q = head2;


java            if(head1.item <= head2.item){
                newhead = head1;
                p = p.next;
            }
            else{
                newhead = head2;
                q = q.next;
            }
            r = newhead;

            while(p!=null && q!=null){
                if(p.item <= q.item){
                    r.next = p;
                    p = p.next;
                    r = r.next;
                }
                else{
                    r.next = q;
                    q = q.next;
                    r = r.next;
                }
            }

            if(p!=null){
                r.next = p;
            }
            if(q!=null){
                r.next = q;
            }
            return newhead;
        }
    }



6 復(fù)雜鏈表的復(fù)制

題目：

解法：

代碼：

java    //1. 根據(jù)原始鏈表的每個(gè)節(jié)點(diǎn)創(chuàng)建對(duì)應(yīng)的copy節(jié)點(diǎn)
    public void CloneNode(ComplexNode head){
        ComplexNode p = head;
        while(p!=null){
            ComplexNode node = new ComplexNode(p.item,null,null);
            node.next = p.next;
            p.next = node;
            p = node.next;
        }
    }


java    //2. 設(shè)置復(fù)制出來(lái)的節(jié)點(diǎn)的sibling
    public void connectsiblingnodes(ComplexNode head){
        ComplexNode p = head;

        while(p!=null){
            ComplexNode q = p.next;
            if(p.sibling!=null)
            {   
                q.sibling = p.sibling.next;
            }
            p = q.next;

        }
    }


java    //3. 拆分鏈表
    public ComplexNode ReconnectNodes(ComplexNode head){
        ComplexNode p = head;
        if(p!=null){    
            ComplexNode newhead = p.next;
            ComplexNode q = newhead;
            while(q.next!=null){
                p.next = q.next;
                p = q.next;
                q.next = p.next;
                q = p.next;
            }
            return newhead;
        }
        else{
            return null;
            }
        }


7 尋找第一個(gè)公共節(jié)點(diǎn)

題目：輸入兩個(gè)鏈表，找出第一個(gè)公共節(jié)點(diǎn)。

解法：Y形

代碼：

java    public Node findfirstcommonnode(Node head1, Node head2){
        Node p = head1;Node q = head2;
        int length = int length1 = int length2= 0;
        while(p!=null){
            length1 = length1 + 1;
            p = p.next;
        }
        while(q!=null){
            length2 = length2 + 1;
            q = q.next;
        }

        p = head1;q = head2;

        if(length1>length2){
            length = length1 - length2;
            while(length>0){
                p = p.next; length--;
            }
        }
        if(length10){
                q = q.next; length--;
            }
        }
        while(p!=null&&q!=null&&p.item != q.item){
                p = p.next; q = q.next;
            }
        return p;
    }


想更一進(jìn)步的支持我，請(qǐng)掃描下方的二維碼，你懂的~