/**
* 節(jié)點(diǎn)定義
**/
static class Node {
        Integer data;
        Node next;

        @Override
        public String toString() {
            return this.data.toString();
        }
 }
/**
* 生成節(jié)點(diǎn)數(shù)據(jù)
**/
static Node readyNode() {
        Node linkNode1 = new Node();
        linkNode1.data = 1;
        Node linkNode2 = new Node();
        linkNode2.data = 2;
        Node linkNode3 = new Node();
        linkNode3.data = 3;
        Node linkNode4 = new Node();
        linkNode4.data = 4;
        Node linkNode5 = new Node();
        linkNode5.data = 5;
        Node linkNode6 = new Node();
        linkNode6.data = 6;
        linkNode1.next = linkNode2;
        linkNode2.next = linkNode3;
        linkNode3.next = linkNode4;
        linkNode4.next = linkNode5;
        linkNode5.next = linkNode6;
        return linkNode1;
    }

/**
* 遞歸方式反轉(zhuǎn)
**/
static Node reverse(Node head) {
        //我們從原鏈表的頭結(jié)點(diǎn)開(kāi)始
        Node cur = head;
        //遞歸到原鏈表的尾節(jié)點(diǎn)結(jié)束。遞歸到了尾節(jié)點(diǎn)的時(shí)候就返回當(dāng)前節(jié)點(diǎn)
        if(cur.next == null){
            return cur;
        }else{
            Node reHead = reverse(cur.next);
            cur.next.next = cur;
            cur.next = null;
            return reHead;
        }

    }

/**
* 循環(huán)方式反轉(zhuǎn)
**/
static Node reverse2(Node pHead) {
        if (pHead == null) {
            return pHead;
        }
        Node prev = null;
        while (pHead != null) {
            //保存next
            Node temp = pHead.next;
            //反轉(zhuǎn)
            pHead.next = prev;
            //移動(dòng)prev
            prev = pHead;
            //移動(dòng)pHead
            pHead = temp;
        }
        return prev;
    }

/**
** 內(nèi)置法
** LinkedList沒(méi)有提供反轉(zhuǎn)鏈表的相關(guān)函數(shù)，以下是通過(guò)foreach實(shí)現(xiàn)鏈表反轉(zhuǎn)
**/
static LinkedList reverse(LinkedList linkedList) {
    LinkedList<Object> newLinkedList = new LinkedList<>();
    for (Object object : linkedList) {
        newLinkedList.add(0, object);
    }
    return newLinkedList;
}