0206-反转链表

反转链表

方案一

在原链表之前建立一个dummy node，因为首节点会变，然后从head开始，将之后的一个节点移到dummy node之后，重复此操作知道head成为末节点为止。

借助单链表实现

C-源代码

#include <stdlib.h>

#include "LinkList.h"

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

void test_0206(void)
{
    int arr[5] = { 5, 4, 3, 2, 1 };
    struct ListNode *l1 = createNode(arr, sizeof(arr) / sizeof(arr[0]));
    printNode(l1);
    
    struct ListNode *ret = reverseList(l1);
    printNode(ret);
}

Swift实现

func reverseList(_ head: ListNode?) -> ListNode? {
        
        var cur: ListNode? = head
        var pre: ListNode? = nil
        
        while cur != nil {
            
            let temp: ListNode? = cur?.next
            cur?.next = pre
            pre = cur
            cur = temp
        }
        
        return pre
    }

方案二

不断的进入递归函数，直到head指向最后一个节点，p指向之前一个节点，然后调换head和p的位置，再返回上一层递归函数，再交换p和head的位置，每次交换后，head节点后面都是交换好的顺序，直到p为首节点，然后再交换，首节点就成了为节点，此时整个链表也完成了翻转

C-源代码

struct ListNode* reverseList(struct ListNode* head) {
    
    if (!head || !head->next) {
        
        return head;
    }
    
    struct ListNode *node = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    
    return node;
}

Swift实现

func reverseListDG(_ head: ListNode?) -> ListNode? {
        
        if head == nil || head?.next == nil {
            
            return head
        }
        
        let h = reverseListDG(head?.next)
        head?.next?.next = head
        head?.next = nil
        
        return h
    }

参考Grandyang