反转链表--迭代和递归

ゝ一世哀愁。 2023-07-24 13:12 37阅读 0赞

1，leetcode网址

[https://leetcode-cn.com/problems/reverse-linked-list/][https_leetcode-cn.com_problems_reverse-linked-list]

2，题目

反转一个单链表。

**示例:**

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

3，源码一、迭代：

class Solution {
        public ListNode reverseList(ListNode head) {
    
            /**
             * 思路：
             * 迭代法：
             * 用两个指针存放节点：指针1：存放当前节点；指针2：存放前一个节点。
             * 1，将当前节点的下一个节点暂存；
             * 2，当前节点的下一个节点指向前一个节点
             * 3，前一个节点往后移动
             * 4，当前节点往后移动
             */
    
            ListNode pre = null;
            ListNode cur = head;
    
            while (cur != null){
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
    
            return pre;
        }
    }

4，源码二，递归

/**
             * 使用递归思想。
             * 即假设在我之后的的节点已经都已经逆序了，就剩我、我的下一个 以及我之前所有的。
             * 为了达到改目的，则会需要将当前节点的下一个节点的下一个节点指向自己。
             * n1->n2->n3->……->n(k-1)->n(k)->n(k+1)<-n(k+2)<-……<-nm;
             * 即head.next.next = head;
             * 同时为了避免循环指针，所以，自己或者自己的下一个为空时，返回自己，即为逆序完成。
             */
            if(head == null || head.next == null){
                return head;
            }
    
            ListNode p = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return p;

图解

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70][]

[https_leetcode-cn.com_problems_reverse-linked-list]: https://leetcode-cn.com/problems/reverse-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70]: /images/20230528/d713d33f9ba24d709af7e3cfe27cf998.png