面试不可不会的单链表反转

链表反转是面试中常考的一道题,这道题看起来简单,但是能一遍写出 bug free 的代码相当不容易,本文主要提供递归和迭代两种解题方法,供大家参考。

题目

 

 

 

举栗

 为了便于理解,以 1->2->3->NULL 为栗子,如下图示:

 

递归解法

链表具有天然的递归性,一个链表例如:1->2->3->NULL,可以看成以值为 1 的节点作为头节点后面挂接一个更短的(以值为 2 的节点为头节点)的链表,即1->更短的链表(以值为2的节点作为头节点),同理以值为2的节点作为头节点后面也挂接一个更更短的链表(以值为3的节点作为头节点);依次类推,如下图示。

 

 

 

 有了这样的思考,链表反转就可以先翻转头节点后面挂接的更短的链表,然后再在翻转后的更短链表的后面挂接之前的头节点。具体如下图示:

 

 Show me the Code

// C语言版本
struct ListNode* reverseList(struct ListNode* head){
    /* 特判 */
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    /* 翻转头节点(节点值为 1 的节点) 后面挂接的链表(以节点值为 2 的节点作为头节点) */
    /* 翻转之后变成 3->2 */
    struct ListNode *node = reverseList(head->next); 
    /* 将头节点(节点值为 1 的节点)挂接在翻转之后的链表的后面(也就是节点值为 2 的节点的后面) */     
    head->next->next = head; 
    /* 将尾节点的下一节点置空 */                            
    head->next = NULL;                               
    return node;
}

  

#python3 版本
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head
        node = self.reverseList(head.next)
        head.next.next = head;
        head.next = None;
        return node;

迭代(双指针)解法

可以用双指针来做,用一个指针 next 记录当前节点的后一节点,另外一个指针 pre 记录当前节点的前一个节点,如果当前节点是头节点,则 pre 为空指针,还是以链表:1->2->3->NUL为栗子,具体如下图示。

 

 

 

 

 

Show me the Code

// C语言版本
struct ListNode* reverseList(struct ListNode* head){
    /* 记录当前节点的前一节点 */
    struct ListNode* pre = NULL; 
    while (head != NULL) {
        /* 记录当前节点的后一节点 */
        struct ListNode* next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

  

// go语言版本
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil
    for head != nil {
        next := head.Next
        head.Next = pre;
        pre = head
        head = next
    }
    return pre
}

  

 

相关推荐

发表评论

路人甲

网友评论(0)