Java

java如何实现反转列表

小亿
88
2023-10-22 08:18:59
栏目: 编程语言

可以使用递归或迭代的方式来实现反转链表。

递归方式:

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

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 如果链表为空或只有一个节点,无需反转,直接返回原链表头节点
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode newHead = reverseList(head.next); // 反转以head.next为头节点的子链表
        head.next.next = head; // 将head节点连接到反转后的子链表的尾部
        head.next = null; // 将head节点的next置为null
        
        return newHead; // 返回新的头节点
    }
}

迭代方式:

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

public class Solution {
    public ListNode reverseList(ListNode head) {
        // 如果链表为空或只有一个节点,无需反转,直接返回原链表头节点
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode prev = null; // 当前节点的前一个节点
        ListNode curr = head; // 当前节点
        
        while (curr != null) {
            ListNode next = curr.next; // 当前节点的下一个节点
            curr.next = prev; // 反转指针指向前一个节点
            prev = curr; // 更新当前节点的前一个节点
            curr = next; // 更新当前节点为下一个节点
        }
        
        return prev; // 返回新的头节点
    }
}

以上是两种常见的反转链表的实现方式。

0
看了该问题的人还看了