算法17(递归)-反转单链表

算法递归链表

发布时间 : 2020-07-04 16:30

字数:519 阅读 :

评论:

题目描述：
Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

采用递归的思路
思路：1.不要想递归每一步是怎样完成的，只需要关注递归的一级：每一级可以看做是下面这种情况

head---->head.next---->null，每一级都是这样的一个小子问题

2.递归终结的条件是什么：只有一个节点或者是没有节点了就递归结束

3.本级递归需要做的事情是什么：交换两个链表的指向：head.next–>null,head.next.next = head

下面就是具体的代码实现

package com.cxy.linkedtable;

/**
 * Reverse a singly linked list.
 *
 * Example:
 *
 * Input: 1->2->3->4->5->NULL
 * Output: 5->4->3->2->1->NULL
 * Follow up:
 *
 * A linked list can be reversed either iteratively or recursively. Could you implement both?
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ReverseSLList {

  public ListNode reverseList(ListNode head) {
    //采用递归调用的方式进行反转，不要在乎内部的细节，关注如下几点
    //    1.递归的终止条件：交换两个节点，如果只有一个节点或者是没有节点就可以停止了。
    //    2.本级递归需要给下级递归传递什么：给下级传递的就是当前结点的下一个节点
    //    3.本次递归做什么： 本次递归需要交换两个节点。
    if(head == null || head.next == null){
      return head;
    }
    //移动指针指向
    ListNode res = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return res;
  }

  public static void main(String[] args) {

    ReverseSLList slList = new ReverseSLList();
    ListNode l1 = new ListNode(1);
    l1.next = new ListNode(2);
    l1.next.next = new ListNode(3);
    ListNode node = slList.reverseList(l1);
    System.out.println(node.toString());
  }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com