题目描述:
反转一个单链表.
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
迭代解法
- /**
- Definition for singly-linked list.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int x) { val = x; }
- }
- */
- class Solution {
- public ListNode reverseList(ListNode head) {
- ListNode pre = null;
- ListNode next = null;
- while(head!=null){
- next = head.next;
- head.next = pre;
- pre = head;
- head = next;
- }
- return pre;
- }
- }
对代码进行解释:
1, 准备两个空节 pre 和 next 点进行后续的操作, 其中 pre 保存 head 之前的节点, next 做临时变量;
2, 如果 head 不空便进入循环体, 转 3; 否则退出循环, 返回 pre, 程序结束.
3, 首先对临时变量 next 进行赋值, 赋值为 head 的 next 值, 以便操作过程中链表不断, 转 4;
4, 为 head 的 next 赋值为 pre(head 的前一个元素), 转 5;
5, 将 pre 赋值为当前的 head 的值, 转 6;
6, 将 head 向后移动一位, 赋值为 next 当前值, 转 2.
提交结果截图:
递归解法
- /**
- * Definition for singly-linked list.
- * public class ListNode {
- * int val;
- * ListNode next;
- * ListNode(int x) { val = x; }
- * }
- */
- class Solution {
- public ListNode reverseList(ListNode head) {
- //1. 基本问题的解
- if(head == null || head.next == null){
- return head;
- }
- //2. 将大问题分解成小问题
- ListNode reve = reverseList(head.next);
- //3. 将小问题的解变成大问题的解
- head.next.next = head;
- head.next = null;
- return reve;
- }
- }
对代码进行解释:
1, 首先看递归头, 也就是问题的基本问题: 如果传入的是空或者只有一个节点, 不用反转直接返回就可以;
2, 将大问题分成小问题: 就是反转 head.next 及其后面的节点组成的链表即可;
3, 将小问题的变成大问题的解: 将原 head.next 的 next 指向 head, 原 head 的 next 变成空即可.
提交结果截图:
以上便是反转链表的迭代与递归两种解法.
来源: http://www.bubuko.com/infodetail-3394258.html