两种方法解决反转链表

一、题目

二、代码 

递归

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { //递归出口 if(head == null || head.next == null){ return head; } //返回的是新的头指针，如果原链表是1->2->3->4->5，则reverseList（）则是 2<-3<-4<-5 <--(新头指针) ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } }

头插法 

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null){ return head; } ListNode dummy = new ListNode(0); dummy.next = head; //先对第一个节点处理的目的是为了防止有环。 ListNode p = head; ListNode q = p.next; p.next = null; while(q != null){ p = q; q = p.next; p.next = dummy.next; dummy.next = p; } return dummy.next; } }

三指针

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head == null || head.next == null){ return head; } //定义3指针 前 当前 后 ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode after = cur.next; cur.next = prev; prev = cur; cur = after; } return prev; } }