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; }