最近在LeetCode做题目,遇到一个反转链表的题目.
|
1 2 3 4 5 6 7 |
反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL |
迭代
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode *tmpHead = head, *nextNode; if (NULL == head) { return head; } while (NULL != head->next) { // 把当前 '头结点' 的下一个移动到 `真正的头结点` nextNode = head->next; head->next = head->next->next; nextNode->next = tmpHead; tmpHead = nextNode; } return tmpHead; } |
递归
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
// 反转一个单链表。(递归的方法) // // 示例: // // 输入: 1->2->3->4->5->NULL // 输出: 5->4->3->2->1->NULL /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { if (NULL == head) { return NULL; } else if (NULL == head->next) { return head; } struct ListNode *currNode = reverseList(head->next); head->next->next = head; head->next = NULL; return currNode; } // reverseList([1, 2, 3, 4, 5]) { // // reverseList([2, 3, 4, 5]) { // // reverseList([3, 4, 5]) { // // reverseList([4, 5]) { // // reverseList([5]) { // // // 1. 这里 next 为 NULL, 所以返回当前自己 // return 5; // } // // // 2. 这一步我们需要拿到 5 的指针指向 4 // // 并把 4 的 next 置空 // [4, 5]->next->next = [4, 5]; // [4, 5]->next = NULL; // // return [5, 4]; // } // // // 3. 这里的参数里实际上 5 已经被内层递归置为 NULL // // 这一步我们需要拿到 4 的指针,然后把它指向 3 // // 并把 3 的 next 置空 // [3, 4, '5']->next->next = [3, 5]; // [3, 4]->next; // // return [5, 4, 3]; // } // // // 4. // [2, 3, '4', '5']->next->next = [2, 3, '4', '5']; // [2, 3]->next = NULL; // // return [5, 4, 3, 2]; // } // // // 5. // [1, 2, '3', '4', '5']->next->next = [1, 2, '3', '4', '5']; // [1, 2]->next = NULL; // // return [5, 4, 3, 2, 1]; // } |
