Preface 单链表的反转,按K反转等各种考点变体。 处理单链表时, 尽量采用递归实现: 1 因为递归代码简洁+优美,节省时间,并且不容易出错,是面试优选策略。 2 在面试时间比较宝贵的情况下,尽量预留时间展示自己的才能。 1 反转单链表(基础) 单链表结构定义如下: 1 2 3 4 5 6 // Definition for singly-linked list. struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; 方法一: 递归实现(尾插法) 1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public: //尾插法 ListNode* reverseList(ListNode* head) { if(head == NULL || head->next == NULL) { return head; } auto tail = reverseList(head->next); head->next->next = head; head->next = NULL; return tail; // became new head } }; 方法二: 循环实现(头插法) 双指针,头插法: 1 2 3 4 5 6 7 8 9 10 11 ListNode* reverseList(ListNode *head) { ListNode *pNewHead……

阅读全文