题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路：
两个指针，起始位置都是从链表头开始，第一个比第二个先走K个节点，当第一个走到链表尾时，第二个指针的位置就是倒数第k个节点。(两指针始终相聚k个节点)
注意边界条件：
1.链表不能一开始就是空的。
2.当链表只有5个节点时，若k=5,则返回第1个节点；若K>5,统一返回NULL。
边界条件十分影响case通过率！！！
#include "../stdafx.h" #include <stdio.h> #include <stdlib.h> #include <vector> #include <iostream> using namespace std; //链表基本操作：https://blog.csdn.net/wabil/article/details/65627058 //定义链表结构体类型 typedef struct TagList{ int val; struct TagList *next; }List; //创建链表 List *create_list(int val){ List *head = new List; if (head == NULL){ return NULL; } head->val = val; head->next = NULL; return head; } //插入节点数据(倒序插入) List *insert_TagList(List *head, int val){ List *temp; if (head == NULL){ return NULL; } temp = new List; //与 List *temp = new List;有区别吗？ temp->val = val; temp->next = head; //head = temp; //head与temp地址相同，temp变化会立即引起Head值变化 //return head; return temp; } //打印链表倒数第k个节点(两个指针相隔k步，一个走到链表尾，另一个即处于倒数第k位) List* FindKthToTail(List* pListHead, unsigned int k) { List* pListHead1 = pListHead; if (pListHead==NULL){ return nullptr; //判断非空 } int i = 1; for (;pListHead != NULL; i++){ //同时满足两个条件 if (i > k){ pListHead1 = pListHead1->next; } pListHead = pListHead->next; } printf(" %d", i); //for循环结束后，i=链表节点个数+1 if (i - 1 < k){ return NULL; //边界条件：k>链表长度 (当5个节点的链表要返回第k(k>=6)个节点，统一返回NULL) } else{ return pListHead1; } } //反转链表 List* ReverseList(List* pHead) { if (pHead == NULL){ return nullptr; } List *next = NULL; List *pre = NULL; while (pHead != NULL){ next = pHead->next; //预先存储下一个链表节点，防止反转时链表断裂 pHead->next = pre; pre = pHead; pHead = next; } return pre; } //从尾到头打印链表 vector<int> printListFromTailToHead(List* head) { //if (head == NULL){ // return -1; //}//由于必须返回vector，这里直接过滤掉头为空的情况 //方法1：遍历链表，逆序插入vector vector<int> array; if (head != NULL){ while (head != NULL){ //array.insert(array.begin() + 3, head->val);//插入到第三个元素之后(即第四个元素,索引为3) array.insert(array.begin(), head->val);//遍历节点，插入vector首位 head = head->next; } return array; } ////方法2：翻转链表然后输出 //List *pre = ReverseList(head); //vector <int> array; //int i = 0; //for (; pre != NULL; i++){ // //array[i] = pre->val; //vector不能按数组索引赋值，可以insert或者push_back // array.push_back(pre->val); // pre = pre->next; //} //return array; } List* Merge(List* pHead1, List* pHead2) { /* //1.递归版本 if (pHead1 == NULL){ //边界条件非空判断 return pHead2; } if (pHead2 == NULL){ return pHead1; } List* pHead = NULL; if (pHead1->val <= pHead2->val){ pHead = pHead1; pHead->next = Merge(pHead1->next, pHead2); } else{ pHead = pHead2; pHead->next = Merge(pHead1,pHead2->next); } return pHead; */ //2.非递归版本 if (pHead1 == NULL){ //边界条件非空判断 return pHead2; } if (pHead2 == NULL){ return pHead1; } //List* pHead = new List; //Oxcccc<val=?? next=??> //List* pHead = NULL; //0x000<NULL> //定义为NULL后无法添加val，next属性(pHead->val=3;之类会报错) //但是可以将链表整个赋给空节点(如pHead=pHead1; pHead=pHead1->next;) //List *pHead=new List; //List *current = pHead; //是指向同一个地址还是指内容？？ List *pHead = NULL; List *current = NULL; while (pHead1 != NULL && pHead2 != NULL){ if (pHead1->val <= pHead2->val){ //pHead->val = pHead1->val; if (pHead == NULL){ pHead = current = pHead1; } else{ current->next = pHead1; current = current->next; } pHead1 = pHead1->next; } else{ //pHead->val = pHead2->val; if (pHead == NULL){ pHead = current = pHead2; } else{ current->next = pHead2; //pHead也会一起变化， 整个过程中current作用？？？ current = current->next; } pHead2 = pHead2->next; } //pHead = pHead->next;//相当于去掉之前的一个节点，进入到下一个节点 } if (pHead1 != NULL){ current->next = pHead1; //当其中一个遍历完了的时候，直接将合并链表的next指向非空链表 } else{ current->next = pHead2; } return pHead; } int main(void){ int i = 0; List *head = create_list(100); List *buf; /* //倒序插入节点 for (i = 1; i <= 10; i++){ head = insert_TagList(head, 100 + i); } i = 0; buf = head; cout << " 倒序插入节点："<<endl; while (buf != NULL){ printf("Data[%02d]:%d ", i++, buf->val); buf = buf->next; }*/ /* //输出倒数第K个节点 head = FindKthToTail(head, 12); printf(" Data:%d", head->val);*/ /* //翻转链表 i = 0; buf = ReverseList(head); cout << " 翻转链表：" << endl; while (buf != NULL){ printf("reverse data[%02d]:%d ", i++, buf->val); buf = buf->next; }*/ /* //链表从尾到头进行打印 vector<int> vec = printListFromTailToHead(head); vector<int>::iterator it; cout << " 从尾到头进行打印： "; for (it = vec.begin(); it != vec.end(); it++)//遍历输出vector { cout << *it << endl; }*/ // 2个链表倒序插入节点 List *head1 = create_list(10); head1 = insert_TagList(head1, 8); head1 = insert_TagList(head1, 6); List *head2 = create_list(11); head2 = insert_TagList(head2, 9); head2 = insert_TagList(head2, 7); /*for (i = 5; i > 0; i--){ head = insert_TagList(head, 90 + i); //91-95, 100 } List *head1=head; for (i = 5; i > 0; i--){ head = insert_TagList(head, 80 + i); //81-85,91-95,100 } List *head2 = head;*/ List *head3 = Merge(head1,head2); i = 0; cout << " 合并两个有序链表：" << endl; while (head3 != NULL){ printf("Data[%02d]:%d ", i++, head3->val); head3 = head3->next; } getchar(); return 0; }
参考：//https://blog.csdn.net/wabil/article/details/65627058
2.链表之判断两个单链表相交的位置
链表相交是指存储相同val的地址也要相同，而不是仅仅val相同。
思路：
如果用两个while(head !=NULL)是无法遍历的，因为内循环指针到链表节点末尾的时候，指向为空，不能自动回到表头。
这里 是用p,q代替两个表头；且一个到链表尾的时候就指向另一个的表头，来进行遍历的。
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA==NULL or headB==NULL){ return NULL; } else{ ListNode *p=headA; ListNode *q=headB; while(p!=q){ if(p!=NULL){ p=p->next; } else{ p=headB; } if(q!=NULL){ q=q->next; } else{ q=headA; } } return p; } } };