美文网首页
数据结构与算法-反转链表206(java)

数据结构与算法-反转链表206(java)

作者: 这里有颗小螺帽 | 来源:发表于2020-02-23 10:18 被阅读0次

迭代版反转链表

/**
 * 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;
        while(head != null){
            ListNode Next = head.next; //保存下一节点
            head.next = pre;//当前节点指向前一节点
            pre = head;//当前节点变为前一节点
            head = Next;//下一节点为当前节点
        }
        return pre;
    }
}

迭代版较为简单,具体思路为:将当前节点为 null 作为 while 的终止条件,循环中的逻辑为:
1. 保存当前节点的下一节点
2. 当前节点指向前一节点
3. 当前节点变为前一节点
4. 下一节点变为当前节点

递归版反转链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
       return reverse(null,head);
       
    }

    public ListNode reverse(ListNode pre,ListNode cur){
        if(cur==null)
            return pre;
        ListNode next = cur.next;
        cur.next = pre;
        return reverse(cur,next);
    }
}

递归的3个条件:

  • 大问题可以分为子问题
  • 每个子问题规模相同,逻辑一致,计算方法相同
  • 有终止条件

在这道题中:

  • 大问题为反转链表,可以拆分为的子问题为:先保存当前节点的下一节点,然后将当前节点指向前一节点,当前节点变为前一节点,下一节点变为当前节点
  • 每个子问题的计算方法都相同
  • 终止条件为,当前节点为 null

相关文章

网友评论

      本文标题:数据结构与算法-反转链表206(java)

      本文链接:https://www.haomeiwen.com/subject/bimdqhtx.html