單連結清單 連結清單翻轉

頭結點不變

head 1 2 3 4

建立一個 newhead

不斷從第一個 取下 1,2,3,4

newhead->1

new->2->1

package jiegou;

import com.sun.corba.se.spi.protocol.RequestDispatcherDefault;
import sun.tools.tree.ThisExpression;

import java.util.List;

// 單連結清單
public class SingleLinkDemo {
    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "松江", "及時雨");
        HeroNode heroNode2 = new HeroNode(2, "吳用", "智多星");
        HeroNode heroNode3 = new HeroNode(3, "林沖", "豹子頭");

        SingleLinkList linkList = new SingleLinkList();


        linkList.addByOrder(heroNode3);
        linkList.addByOrder(heroNode2);
        linkList.addByOrder(heroNode1);

//        HeroNode heroNode4 = new HeroNode(3, "林沖", "豹子頭tou");
//
//        linkList.editNode(heroNode4);

        // 删除節點
        //linkList.list();

//        System.out.println("删除節點後");
//        linkList.delete(heroNode1);
//        linkList.delete(heroNode2);
        System.out.println("翻轉之前");
        linkList.list();

//        int numbers = getNodes(linkList.getHead());
//        System.out.println(numbers);
//
//        HeroNode lastNode = findLastNode(linkList.getHead(), 4);
//        System.out.println(lastNode);

        // 連結清單翻轉
        reverseList(linkList.getHead());
        System.out.println("翻轉後的連結清單");
        linkList.list();
    }

    // 查找單連結清單中的倒數第 k個節點
    // 接受 head index 倒數第 index個節點
    // 先把連結清單從頭到尾周遊 得到總數 從第一個開始周遊 size-index

    public static HeroNode findLastNode(HeroNode head,int index)
    {
        if(head.next == null) {
            return head;
        }

        int sum = getNodes(head); // 總數
        if(index <=0 || index > sum){
            return null;
        }

        HeroNode temp = head.next;

        for(int i=0;i<sum-index;i++){
            temp =temp.next;
        }

        return temp;
    }

    // 求單連結清單有效節點個數
    public static int getNodes(HeroNode head) {
        int sum = 0;
        if (head.next == null) {
            return 0;
        }
        HeroNode node = head.next;
        while (node != null) {
            System.out.println(node.name);
            sum++;
            node = node.next;
        }

        return sum;
    }

    public static void reverseList(HeroNode head) {
        // 如果連結清單為空 或者隻有一個無需翻轉
        if(head.next == null || head.next.next == null){
            return ;
        }

        // 輔助指針
        HeroNode temp = head.next;
        HeroNode next = null;// 目前節點的下一個節點
        HeroNode reverseHead = new HeroNode(0,"","");

        while (temp !=null){
            next = temp.next;
            // 相當于 reverhead 與 reverhaed.next中間要插入一個節點 新節點
            // 的 next
            temp.next = reverseHead.next;// 将 temp 的下一個節點指向新的最前端
            reverseHead.next = temp;
            temp = next;// 相當于以前的 temp =temp.next
        }

        head.next = reverseHead.next;

    }
}

// 連結清單管理節點
class SingleLinkList {
    public HeroNode getHead() {
        return head;
    }

    // 初始化一個頭節點
    private HeroNode head = new HeroNode(0, "", "");


    // 添加節點到單向連結清單
    public void add(HeroNode heroNode) {
        // 找到連結清單最後
        //将最後節點的 next 指向這個新節點
        HeroNode temp = head;
        //周遊連結清單
        while (true) {
            // 當 temp.next== null
            if (temp.next == null) {
                break;
            }

            // 沒有找到最後  temp 後移
            temp = temp.next;
        }

        temp.next = heroNode;
    }

    // 編号不能改
    public void editNode(HeroNode heroNode) {
        if (this.head.next == null) {
            return;
        }
        HeroNode temp = head.next;
        Boolean flag = false;
        while (true) {
            if (temp == null) {
                flag = false;
                break;
            }
            if (temp.no == heroNode.no) {
                // 找到了
                flag = true;
                break;
            }

            temp = temp.next;
        }


        if (flag) {
            temp.name = heroNode.name;
            temp.nickname = heroNode.nickname;
        } else {
            System.out.printf("未找到編号=%d的節點\n", heroNode.no);
        }

    }

    public void delete(HeroNode heroNode) {
        if (this.head.next == null) {
            System.out.println("沒有節點");
            return;
        }


        HeroNode temp = head;
        boolean flag = false;

        while (true) {

            if (temp.next == null) { // 找到最後都沒找到
                break;
            }

            if (temp.next.no == heroNode.no) { // 找到的是要删除的前一個節點
                flag = true;
                break;
            }

            temp = temp.next; // 後移
        }

        if (flag) {
            temp.next = heroNode.next;// 跨過要删除的
        }

    }


    // 按順序添加節點  如果有排名 添加失敗
    public void addByOrder(HeroNode heroNode) {
        // 頭結點不能動
        // 因為是單連結清單 temp是位于添加位置的前一個節點 否則插入不了
        HeroNode temp = head;
        boolean flag = false; // 辨別添加的編号是否存在 預設 false

        while (true) {
            if (temp.next == null) {
                // 連結清單結尾
                break;
            }

            if (temp.next.no > heroNode.no) // 在 temp 後面插入
            {
                break;
            } else if (temp.next.no == heroNode.no) {
                flag = true;// 編号存在
                break;
            }

            temp = temp.next; // 後移 直到找到
        }

        //temp 就是在他後面添加
        if (flag) {
            System.out.printf("編号%d存在\n", heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }

    }

    // 顯示連結清單
    public void list() {
        // 判斷連結清單是否為空
        if (head.next == null) {
            System.out.println("連結清單為空");
            return;
        }

        HeroNode temp = head.next;

        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }


}

// 節點
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next; //指向下一個節點

    // 構造方法
    public HeroNode(int hNo, String HName, String HNickName) {
        this.no = hNo;
        this.name = HName;
        this.nickname = HNickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
               // ", next='" + next + '\'' +
                '}';
    }

}