NC78 反转链表

解题思路

如题,我们需要做的就是将一个链表反转。那么,我这里有两种做法(当然可能还存在其他的解题思路)。
第一种,即是迭代。next指针保存当前head节点的下一个节点,因为当前head所在的节点即将要指向前面的节点了,如果不用next指针保存的话,那么我们就无法找到后续要反转的节点了。如图。
图片说明
就这样,一直迭代,每一轮反转以后,我们将当前的head赋值给prev,然后再将next记录的下一个要反转的节点地址赋值给head,这样我们就可以反转整条链表啦。

以下附上我第一种解题思路的代码:

 public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode prev=null,next;
        while(head!=null){
            next=head.next;
            head.next=prev;
            prev=head;
            head=next;
        }
        return prev;
    }

第二种,即是递归。这个需要一点点递归基础去看懂,即利用递归的特性,从链表的末尾开始反转。

    public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode newHead=ReverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }