链表反转（Java实现）

对一个单链表进行反转，有两种方法可以实现，一种是迭代法，一种是递归法

示例： 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

1.迭代法：维护两个指针，curr指向当前需要修改next指针的节点，prev指向curr指向的节点的next指针修改后所指向的节点，从前向后遍历链表，同时进行链表的反转

class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; } }

2.递归法：利用递归直接得到链表尾节点，然后从后向前回溯反转链表

class Solution { //newHead用于记录反转链表后的链表头节点 ListNode newHead=null; public ListNode reverseList(ListNode head) { reverse(head); return newHead; } public ListNode reverse(ListNode node) { if(node==null||node.next==null) { newHead=node; return node; } //利用递归，从后向前更改每个节点的next指针的指向 ListNode nextNode=reverse(node.next); nextNode.next=node; node.next=null; return node; } }