反转单链表
1、题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例:
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
这道题目比较暴力的算法是新创建一个链表，把旧链表的数据一个一个挪下来，进行头插。
这样就可以解答出来，不过这种方式的时间复杂度是0(N),空间复杂度O(N)，那么我们是否可以简化一下复杂度呢？很显然我们要想反转链表，遍历一遍是必须的，所以我们是否可以节省空间，对原链表下手，而不开辟新的空间呢？答案是肯定的。
2、解：三指针反转单链表
只需要注意一下最后需要返回的头是什么就可以了。
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev=NULL; struct ListNode* cur=head; struct ListNode* next=NULL; if(head==NULL) { return NULL; } while(cur) { next=cur->next; cur->next=prev; prev=cur; cur=next; } return prev; }
合并两个有序链表
1、题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
两个指针对两个链表进行遍历，小的尾插，即可。需要注意的是当一个链表结束的时候另一个链表还没结束的处理。
2、解:
带哨兵位的链表进行解答在找头节点的时候比较方便。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* guard=(struct ListNode*)malloc(sizeof(struct ListNode)); guard->next=NULL; struct ListNode* cur1=list1; struct ListNode* cur2=list2; struct ListNode* cur=guard; while(cur1&&cur2) { if(cur1->val<cur2->val) { cur->next=cur1; cur1=cur1->next; } else { cur->next=cur2; cur2=cur2->next; } cur=cur->next; } while(cur1) { cur->next=cur1; cur1=cur1->next; cur=cur->next; } while(cur2) { cur->next=cur2; cur2=cur2->next; cur=cur->next; } struct ListNode* newhead=guard->next; free(guard); guard=NULL; return newhead; }
链表的回文结构
1、题目描述
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例：
1->2->1->2 返回: true
1->2->3->2->1 返回: true
1->2->3->4->2 返回: false
对于回文类的题目，比较快捷的方式就是找到链表的中间节点，对后半段链表进行翻转，然后和前半段链表进行比较，这种方式是比较便捷的。
这里还有一个问题，如何查找链表的中间节点，可能有的方式是遍历计数，然后找中间节点，这种方式是比较低效的，博主想给大家介绍的方式是采用快慢指针的方式查找中间节点。
演示:
通过观察可以发现，快慢指针对于奇数个和偶数个的处理不一致，只需添加限定条件即可。
找到中间节点后，反转链表我放在上面了，可以直接拿来用，所以，看代码：
class PalindromeList { public: struct ListNode* middleNode(struct ListNode* head) { struct ListNode* fast,*slow; fast=slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; } return slow; } struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur=head; struct ListNode* prev=NULL; struct ListNode* next=NULL; while(cur) { next=cur->next; cur->next=prev; prev=cur; cur=next; } return prev; } bool chkPalindrome(ListNode* A) { // write code here //快慢指针找到一半，然后前后比较 struct ListNode* mid=middleNode(A); struct ListNode* rmid=reverseList(mid); struct ListNode* cur=A; while(cur&&rmid)//奇数个和偶数个都要考虑到 { if(cur->val!=rmid->val) return false; cur=cur->next; rmid=rmid->next; } return true; } };
链表中倒数第k个节点
1、题目描述
输入一个链表，输出该链表中倒数第k个结点。
输入：1，{1,2,3,4,5}
返回值：{5}
如果掌握了快慢指针的精髓，那么这道题目对于大家来说是非常轻而易举的，因为这道题目让找到倒数第k个节点，这个节点和最后一个节点相差的不就是k，所以慢指针和快指针相差k，而快指针走到尾不就行了？不过这道题目还有很多细节的地方需要讲述。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* fast=pListHead; struct ListNode* slow=pListHead; if(fast==NULL) return NULL; while(k--) { fast=fast->next; if(k>0&&fast==NULL) return NULL; } while(fast) { slow=slow->next; fast=fast->next; } return slow; }
这段代码是可以跑过去的，不过可读性比较差，还可以优化。
主要问题是在这两处:
这处代码主要考虑有可能为NULL的问题。
这段代码为什么说它可读性差呢？主要就是k>0这部分让人摸不着头脑。为什么会这样写呢？这也是为了解决一些特殊情况:
如果k是恰好为这个链表的总长度，那么倒数第k个节点势必是第一个节点，但是这时fast已经指向NULL，为了则会返回NULL，这显然是错误的，但是这句代码是为了解决k大于整个链表长度时倒数第k个节点为NULL的情况，显然不能删，只好更改为这样，有没有更好的解决办法？答案肯定是有的:
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here //快慢指针 //找倒数第四个 struct ListNode* fast=pListHead; struct ListNode* slow=pListHead; if(pListHead) { while(k--) { if(fast==NULL) return NULL; fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } } return slow; }
这样处理对代码进行了进一步的优化。
