單連結清單的反轉如何實作

題目描述

輸入一個連結清單，反轉連結清單後，輸出新連結清單的表頭，反轉後的結果如下圖所示。

思路分析

代碼實作

節點類

package day04;

import lombok.Data;

/**
 * @Author yqq
 * @Date 2022/05/06 18:45
 * @Version 1.0
 * 節點類
 */
@Data
public class Node {
    /**
     * 用于儲存節點中的資料
     */
    private Object data;
    /**
     * 用于儲存下一個節點的位址值
     */
    private Node next;

    public Node(Object data) {
        this.data = data;
    }

    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }
}      

實作類

package day04;

/**
 * @Author yqq
 * @Date 2022/05/06 18:44
 * @Version 1.0
 */
public class ReverseLinkedList {
    public static void main(String[] args) {
        //建立一個單連結清單
        Node lastNode = new Node(44);
        Node node3 = new Node(33,lastNode);
        Node node2 = new Node(22,node3);
        Node headNode = new Node(11,node2);
        System.out.print("反轉之前:");
        print(headNode);
        System.out.println();
        Node reverse = reversLinked(headNode);
        System.out.print("反轉後:");
        print(reverse);

    }

    /**
     * 實作單連結清單的反轉
     * @param headNode 需要反轉單連結清單的首節點
     * @return
     */
    public static Node reversLinked(Node headNode){
        //判斷headNode為null和單連結清單隻有一個節點的情況
        if (headNode == null || headNode.getNext() == null)
            return headNode;
        //定義一個節點用于儲存反轉後連結清單的首節點
        Node reverse = null;
        //定義一個循環，用于實作單連結清單的反轉操作
        while (headNode != null){
            //獲得headNode的下一個節點
            Node nextNode = headNode.getNext();
            //把headNode插入到反轉後的連結清單的最前面
            headNode.setNext(reverse);
            //更新反轉後連結清單的首節點
            reverse = headNode;
            //更新需要反轉連結清單的首節點
            headNode = nextNode;
        }
        //傳回反轉後連結清單的首節點
        return reverse;
    }
    /**
     * 實作單連結清單的周遊操作
     * @param headNode
     */
    public static void print(Node headNode){
        //定義一個臨時節點，用于輔助單連結清單的周遊操作
        Node tempNode = headNode;
        //定義一個循環，用于是實作單連結清單的周遊操作
        while (tempNode != null){
            //輸出tempNode中儲存的資料值
            System.out.print(tempNode.getData()+" ");
            //讓tempNode指向它的下一個節點
            tempNode = tempNode.getNext();
        }
    }
}