反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

遍历实现

三个指针分别指向当前节点和前一个后一个节点,让当前节点的下一个节点从原来的下一个节点改成指向前一个节点,便实现了两个节点的反转,依次遍历就实现了所有节点反转

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null) return head;
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur.next!=null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return cur;
    }
}

递归实现

暂时还没理解~

标签: leetcode, java

添加新评论