算法-反轉連結清單

反轉連結清單

題目

描述

輸入一個連結清單，反轉連結清單後，輸出新連結清單的表頭。

示例1

輸入：

{1,2,3}

複制

傳回值：

{3,2,1}

答案一：

//節點實作
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
           

//反轉實作 遞歸 類似冒泡排序
public static ListNode reverseList(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }
        ListNode temp = head.next;
        ListNode newHead = reverseList(head.next);
        temp.next = head;
        head.next = null;
        return newHead;
    }

           

答案二：

//節點實作
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
           

//反轉實作 指針偏移
public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode temp;
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        head.next = null;
        return pre;
    }