题目
题目一:.反转一个单链表
思路1
可以用三个节点依次翻转,中间节点指向反转,交换三个节点指针,更新,直到原链表遍历完。但这里要求链表至少有2个节点(第三个节点可以是NULL)。所以,我们可以在开始进行判断,当链表为空或者链表少于2个节点。我们直接返回头指针就行。
空链表
直接返回
一个节点
反转过来就是自己本身。所以,可以直接返回
思路2
逐个头插到一个新链表,不断更新newhead。cur与next接替节点。这种思路方便的就是不用分类。
代码1
struct ListNode* reverseList(struct ListNode* head) {if(head == NULL || head->next == NULL)return head;struct ListNode* n1, *n2, *n3;n1 = head;n2 = n1->next;n3 = n2->next;n1->next = NULL;//中间节点不为空,继续修改指向while(n2){//中间节点指向反转n2->next = n1;//更新三个连续的节点n1 = n2;n2 = n3;if(n3)n3 = n3->next;}//返回新的头return n1;
}
代码2
// 取节点头插的思想完成逆置
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* newhead = NULL;struct ListNode* cur = head;while(cur){struct ListNode* next = cur->next;//头插新节点,更新头cur->next = newhead;newhead = cur;cur = next;}return newhead;
}
题目二:链表的中间节点
思路
使用快慢指针,cur每次走两步,prev每次走一步。prev的路程是cur的一半。当cur走完时,prev刚好就是中间那个节点
代码
/*
解题思路:
通过快慢指针找到中间节点,快指针每次走两步,慢指针每次走一步,当快指针走到结尾的时候,慢指针正好走到中间位置
*/
typedef struct ListNode Node;
struct ListNode* middleNode(struct ListNode* head){Node* slow = head;Node* fast = head;while(fast!=NULL && fast->next != NULL){slow = slow->next;fast = fast->next->next;}return slow;
}
题目三:返回倒数的第k个节点
思路
快慢指针,控制区间段。先让fast走k步,再让fast与slow一起走。当fast走完时,slow就是指向倒数第k个节点的指针
代码
/*
解题思路:
快慢指针法 fast, slow, 首先让fast先走k步,然后fast,slow同时走,fast走到末尾时,slow走到倒数第k个节点。
*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {struct ListNode* slow = pListHead;struct ListNode* fast = slow;while(k--){if(fast)fast = fast->next;elsereturn NULL;}while(fast){slow = slow->next;fast = fast->next;}return slow;}
};
题目四:合并两个有序链表
思路
和有序数组的合并思路类似。都是依次比较,取更小的数据插入。不过这里是链表,不方便尾插。所以,我们创建一个带哨兵位的链表,再创建一个尾指针(方便尾插)。依次把更小的数据尾插到新链表上,最后再把新链表的next返回。因为这里给你的是你一个不带哨兵位的链表。所以,你返回的时候也不要带哨兵位的链表。
这里使用哨兵位的链表会很方便。如果你的新链表不带哨兵位,那你还要考虑给新的newhead赋值。
代码
/*
解题思路:
此题可以先创建一个空链表,然后依次从两个有序链表中选取最小的进行尾插操作进行合并。
*/
typedef struct ListNode Node;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){if(l1 == NULL)return l2;else if(l2 == NULL)return l1;Node* head = NULL, *tail = NULL;//创建空链表head = tail = (Node*)malloc(sizeof(Node));tail->next = NULL;while(l1 && l2){// 取小的进行尾插if(l1->val < l2->val){tail->next = l1;tail = tail->next;l1 = l1->next;}else{tail->next = l2;tail = tail->next;l2 = l2->next;}}//剩余元素直接拼接if(l1)tail->next = l1;elsetail->next = l2;Node* list = head->next;free(head);return list;
}
总结
这几道题都是关于链表的,大多题目的思路都和双指针有关。所以,可见双指针在解决链表的一些题目上有很大作用。这可以当成一个题解的基本思路。从双指针出发,根据题目特点进行变型,解决题目。解决这类题目,画图也是一个很好的方法。当你在写代码前,先画图把思路弄清楚,会大大提高你代码的正确率。即使代码错了,也可以通过图来走读你的代码。如果都不行,我们再调试代码。这能提高你解决题目的效率,不然你很有可能是调试了两三个小时都发现不了问题。