【LeetCood206】反转链表

题目 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

答案1： 新建链表，遍历原链表，一个一个头插到新建的链表.直到结点为null public ListNode reverseList(ListNode head) { ListNode secondListHead = null; while(head!=null){ ListNode temp = new ListNode(head.val,secondListHead); secondListHead=temp; head=head.next; } return secondListHead; } 答案2： prev是反转后链表的头，cur是等待反转的链表的头，让rec记录等待反转的链表的头的下一位。 把等待反转的链表的头摘离，也就是cur的next不再是等待反转的链表，而是完成反转链表的头，即cur.next=prev.此时cur成了反转链表的头 此时把反转的链表的头更新成prev,也就是prev=cur. 刚刚说了,rec记录的是等待反转链表的头的下一位,又因为他的头被摘离了,所以rec成了等待反转链表的头.于是让cur=rec(rec的作用是防止待反转链表丢失在内存中) 重复上述操作:先借助cue,用rec记录下下一位结点.摘离头结点,放在反转链表的头位置.更新反转链表的头.cur再重新回到待反转链表的头.往复循环直到cur为null public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur!=null){ ListNode rec = cur.next; cur.next=prev; prev=cur; cur=rec; } return prev; } 答案3:递归 已知reverseList(ListNode head)函数的作用是将以head为头结点的链表反转,并返回反转链表的头结点. 当链表为空,或者只有一个结点时,自然不需要再反转了. 否则的话,先新建next结点记录一下第二个结点. 调用自己,新建newHead结点接收反转后的链表. 已知刚才next结点记录一下第二个结点.反转之后,那么next就成了头结点了.所以此时断开head和链表的连接,并把head接在反转链表的尾巴,即next.next=head. 最后返回newHead. (不用操心去头子链表是如何反转的,只需要做到把头结点接到被处理的子链表的尾部就好了) public ListNode reverseList(ListNode head) { if(head==null||head.next==null){ return head; } ListNode next=head.next; ListNode newHead = reverseList(head.next); head.next=null; next.next=head; return newHead; }