206. reverse linked list

Reverse a singly linked list.
Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

代码

• 迭代的代码

  class Solution {
       public ListNode reverseList(ListNode head) {
          ListNode reverseNode=null;
          ListNode cur=head;
          ListNode toDeal=null;
          while(cur!=null) {
              //拿到待处理的节点
              toDeal =cur;
              cur=cur.next;
              //拿到一边进行连接
              toDeal.next=reverseNode;
              reverseNode=toDeal;
          }
          return reverseNode;
      }
  }
  

• 递归的代码
  代码一

  class Solution {
       public ListNode reverseList(ListNode head) {
          if(head==null||head.next==null)
              return head;
          return toReverse(head,null);
      }
      private ListNode toReverse(ListNode head, ListNode reverse) {
          if(head==null) {
              return reverse;
          }
          ListNode cur=head.next;
          //与另一个链表相连接
          head.next=reverse;
          //
          reverse=head;
          return toReverse(cur,reverse);
      }
  }
  

代码二

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