题目
题目来源leetcode
leetcode地址：206. 反转链表，难度：简单。
题目描述(摘自leetcode)：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例 2： 输入：head = [1,2] 输出：[2,1] 示例 3： 输入：head = [] 输出：[]
本地调试代码：
class ListNode { int val; ListNode next; ListNode() { } ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class Solution { //业务代码 public ListNode reverseList(ListNode head){ ... } public static void main(String[] args) { ListNode node7 = new ListNode(7, null); ListNode node6 = new ListNode(6, node7); ListNode node5 = new ListNode(5, node6); ListNode node4 = new ListNode(4, node5); ListNode node3 = new ListNode(3, node4); ListNode node2 = new ListNode(2, node3); ListNode node1 = new ListNode(1, node2); //反转链表 ListNode listNode = new Solution().reverseList(node1); //遍历 printList(listNode); } private static void printList(ListNode listNode) { if(listNode == null){ return; } System.out.print("["); while(listNode != null){ System.out.print(listNode.val); if(listNode.next != null){ System.out.print(","); } listNode = listNode.next; } System.out.print("]"); } }
题解
No1：双指针法
思路：定义前置指针及当前指针，遍历链表每个节点时移动前置、当前指针，遍历到某个节点时首先使用临时变量存储当前指针的next，紧接着进行反转操作将当前指针指向节点的next指向前置指针，接着两个指针统一往后移即可。
代码：
/** * 双指针法 * @param head * @return */ public ListNode reverseList(ListNode head){ //head为null或一个时 if(head == null || head.next == null){ return head; } //定义两个指针 ListNode temp; ListNode pre = null; ListNode cur = head; while(cur!=null){ temp = cur.next; cur.next = pre; //指针移动，各自向后移动 pre = cur; cur = temp; } return pre; }
NO2：递归解法
思路：当有重复相同的动作时你就可以使用到递归，这里反转链表实际上就有大量相同的反转操作。递归方法参数定义两个，一个是前置指针指向的节点、第二个是当前指针，将当前指针为null情况作为出口返回反转链表后的头节点也就是参数中的前置指针。每个重复方法中的核心操作就是：cur.next = pre;。
代码：
/** * 递归 * @param head * @return */ public ListNode reverseList(ListNode head){ return reverse(null,head); } /** * 反转，其实也就是遍历了一遍 * @param pre * @param cur * @return 原始链表最后一个节点 */ private ListNode reverse(ListNode pre, ListNode cur) { //递归终止条件 if(cur == null){ return pre; } //提前保存下一个节点 ListNode temp = cur.next; //进行链表中某个节点next指向反转 cur.next = pre; return reverse(cur,temp); }
