java如何实现反转列表

58次阅读
没有评论

共计 836 个字符,预计需要花费 3 分钟才能阅读完成。

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

递归方式:

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; // 返回新的头节点 
    }
}

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

丸趣 TV 网 – 提供最优质的资源集合!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-12-20发表,共计836字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)