Java如何翻轉鏈表

本篇內容介紹了“Java如何翻轉鏈表”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

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("打印鏈表反轉前：");
        Utils.print(head);
        ReverseListNode rln = new ReverseListNode();
        System.out.println("打印鏈表反轉后：");
        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 如果是終節點,就會將終結點返回,所以revHead就是終結點
            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是翻轉后的頭結點)=3    <head=3>
        head.next = null;       //3.next=null
        return revHead;
    }

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

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

        newHead = head;		//把舊頭結點賦值給新頭結點
        head = head.next;	//此時的head已經是第二個節點
        newHead.next = null;

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

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

    ListNode reverse4(ListNode L){//TODO
        ListNode head = null;
        ListNode temp ;
        while (L != null){
            temp = L.next;//將第二個節點賦值給tmp
            L.next = head;//將第一個節點指向新的頭結點
            head = L;     //將新的頭結點L賦值給head,用于下次循環
            L = temp;     //下一次迭代中迭代的是第二個節點
        }
        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]);//新節點node
            node.next = head.next;//將頭節點的尾部轉移到新節點的尾部
            head.next = node;//將頭結點尾部指向新節點
        }
        return head.next;
    }
    /**
     *
     *
     打印鏈表反轉前：
     1->2->3->4->
     打印鏈表反轉后：
     ----4,3----
     ----3,2----
     ----2,1----
     4->3->2->1->

     */
}

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