今日写题06work(链表)
题目
题目一：.反转一个单链表
思路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;
else
return 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;
else
tail->next = l2;
Node* list = head->next;
free(head);
return list;
}总结
这几道题都是关于链表的，大多题目的思路都和双指针有关。所以，可见双指针在解决链表的一些题目上有很大作用。这可以当成一个题解的基本思路。从双指针出发，根据题目特点进行变型，解决题目。解决这类题目，画图也是一个很好的方法。当你在写代码前，先画图把思路弄清楚，会大大提高你代码的正确率。即使代码错了，也可以通过图来走读你的代码。如果都不行，我们再调试代码。这能提高你解决题目的效率，不然你很有可能是调试了两三个小时都发现不了问题。