提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

反转链表（剑指offer 24）

2023-03-14 22:46:41 时间

一、题目描述


定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。


示例:

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

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


限制：

0 <= 节点个数 <= 5000


/**
 * 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、迭代 


假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。

        

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。


2、递归 

         

用递归的方式将节点一一连在新链表的头部，则实现了反转。


四、Java代码实现


1、迭代 


class Solution {
    public ListNode reverseList(ListNode head) {
        
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            //先保存后一个节点
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}


2、递归 


/**
 * Definition for singly-linked list.
 * public 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) {
        return doReverse(head, null);
    }
 
    public ListNode doReverse(ListNode node, ListNode list){
 
        if(node == null){
            return list;
        }
 
        //先保存下一个节点
        ListNode temp = node.next;
        //将当前节点接到新建链表的头
        node.next = list;
        return doReverse(temp, node);
    }
}



五、时空复杂度分析


  • 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

  • 空间复杂度：O(1)。


六、其他代码实现

 

在力扣上偷的其他语言的代码，以供参考。

1、C++


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};


2、C


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}


相关文章