反转链表
方案一
在原链表之前建立一个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
}
