Java如何翻轉(zhuǎn)鏈表

本篇內(nèi)容介紹了“Java如何翻轉(zhuǎn)鏈表”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！

package com.lifeibigdata.algorithms.leetcode;


/**
 * Created by lifei on 16/6/30.
 */
public class ReverseListNode {
    public static void main(String[] args) {
        ListNode head=new ListNode(1);
        ListNode n1 =new ListNode(2);
        ListNode n2 =new ListNode(3);
        ListNode n3 =new ListNode(4);
        //初始化鏈表
        head.next = n1 ;
        n1.next = n2;
        n2.next = n3;
        System.out.println("打印鏈表反轉(zhuǎn)前：");
        Utils.print(head);
        ReverseListNode rln = new ReverseListNode();
        System.out.println("打印鏈表反轉(zhuǎn)后：");
        ListNode newHead = rln.reverse4(head);//TODO 3種方式
        Utils.print(newHead);
//        System.out.println("===========create==============");
//        ListNode cln = createList(new int[]{1,2,3,4,5});
//        Utils.print(cln);
    }


    /**
     * 第一輪
     * 3.next (reverse) revHead 4
     * 3.next.next=4.next(賦值前為null)   3
     * 3.next -> null
     * 4 3 null
     *
     *第二輪
     * 2.next.next=3.next(賦值前為null)   2
     * 2.next -> null
     * 4 3 2 null
     *
     *
     *
     * @param head
     * @return
     */
    ListNode reverse(ListNode head){
        if (null == head || null == head.next){//TODO 如果是終節(jié)點,就會將終結(jié)點返回,所以revHead就是終結(jié)點
            return head;
        }
        ListNode revHead = reverse(head.next);
        System.out.println("----"+head.val+","+head.next.val+"----");
        head.next.next = head;  //3.next.next(4.next，此時4是翻轉(zhuǎn)后的頭結(jié)點)=3    <head=3>
        head.next = null;       //3.next=null
        return revHead;
    }

    //“頭插法”思想描述：從鏈表的第一個結(jié)點開始，以每一個結(jié)點為單位，遍歷鏈表，將遍歷到的結(jié)點依次插入到頭結(jié)點的后面
    ListNode reverse2(ListNode head){//TODO
        if (null == head || null == head.next) {
            return head;
        }
        ListNode pre = null;    //新鏈表過程中的頭結(jié)點
        ListNode cur = head;    //cur為遍歷的游標(biāo),同時也是最后返回鏈表的頭結(jié)點
        ListNode next = cur.next;
        while (next != null){   //todo cur為即將插入的節(jié)點,此處是判斷循環(huán)終止的條件
            cur.next = pre;     //將待插入的節(jié)點->新鏈表的頭結(jié)點
            pre = cur;          //將新插入的節(jié)點,作為下一次循環(huán)的頭結(jié)點
            cur = next;         //循環(huán)下一個節(jié)點
            next = cur.next;    //判斷新節(jié)點的下一個節(jié)點,進行循環(huán)
        }
        cur.next = pre;
        return cur;
    }

    //頭插法
    static ListNode reverse3(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }
        ListNode nextHead = null;   //待轉(zhuǎn)置的下一個節(jié)點
        ListNode newHead = null;	//新鏈的頭節(jié)點
        ListNode newn = null;  		//待插入插入的節(jié)點			需要待插入的節(jié)點直接指向新鏈的頭節(jié)點，那么返回新插入的節(jié)點，就是插入之后鏈的頭節(jié)點

        newHead = head;		//把舊頭結(jié)點賦值給新頭結(jié)點
        head = head.next;	//此時的head已經(jīng)是第二個節(jié)點
        newHead.next = null;

        while(head.next != null){	//此時的head是第二個節(jié)點,該節(jié)點為需要加入鏈表的新節(jié)點，即newn; head.next第三個節(jié)點,，
            nextHead = head.next;	//下一次待轉(zhuǎn)置的節(jié)點
            newn = head;			//將要插入的新節(jié)點
            newn.next = newHead;	//新插入的節(jié)點指向 新鏈的頭節(jié)點
            newHead = newn;			//將新插入的節(jié)點作為新鏈的節(jié)點

            // newn.next = newHead.next; //錯誤的  不能用創(chuàng)建鏈表的方式，因為創(chuàng)建鏈表的方式有一個空的頭節(jié)點
            // newHead.next = newn;		 //錯誤的
            head = nextHead;
        }
        newn = head;	//因為每次判斷的是新插入節(jié)點的下一個節(jié)點，所以最后一個節(jié)點不在循環(huán)中，此時的head就是最后一個節(jié)點
        newn.next = newHead;
        return newn;
    }

    ListNode reverse4(ListNode L){//TODO
        ListNode head = null;
        ListNode temp ;
        while (L != null){
            temp = L.next;//將第二個節(jié)點賦值給tmp
            L.next = head;//將第一個節(jié)點指向新的頭結(jié)點
            head = L;     //將新的頭結(jié)點L賦值給head,用于下次循環(huán)
            L = temp;     //下一次迭代中迭代的是第二個節(jié)點
        }
        return head;
    }

    /**
     * 圖示
     * @param head
     * @return
     */
    ListNode reverse5(ListNode head){//TODO
        ListNode pRerverseHead = null;
        ListNode pNode = head;
        ListNode pPrev = null;
        while (pNode != null){
            ListNode next = pNode.next;
            if (next == null){
                pRerverseHead = pNode;
            }
            pNode.next = pPrev;
            pPrev = pNode;
            pNode = next;
        }
        return pRerverseHead;
    }

    static ListNode createList(int[] values){
        ListNode head = new ListNode(0);
        for(int i = 0;i < values.length;i++){
            ListNode node = new ListNode(values[i]);//新節(jié)點node
            node.next = head.next;//將頭節(jié)點的尾部轉(zhuǎn)移到新節(jié)點的尾部
            head.next = node;//將頭結(jié)點尾部指向新節(jié)點
        }
        return head.next;
    }
    /**
     *
     *
     打印鏈表反轉(zhuǎn)前：
     1->2->3->4->
     打印鏈表反轉(zhuǎn)后：
     ----4,3----
     ----3,2----
     ----2,1----
     4->3->2->1->

     */
}

“Java如何翻轉(zhuǎn)鏈表”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！