以下题目均为IO型。
1.给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
题目示例如上：
解题思路：
双指针问题，给定指针prev和cur，从头结点开始往后遍历，分两种情况讨论：
- 假如头节点为要删除的节点
- 假如中间节点为要删除的节点
prev记录要删除节点的前一个节点，cur记录要删除的节点
假如是第一种情况，cur->val == val时，
if(cur == head)//1.头删 { head = cur->next; free(cur); cur = head; }
假如是第二种情况，
prev->next = cur->next; free(cur); cur = prev->next;
完整代码如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ //画图分析才会写 typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode*cur = head; ListNode*prev = head; while(cur) { if(cur->val==val) { if(cur == head)//1.头删 { head = cur->next; free(cur); cur = head; } else//2.中间删除 { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } return head; }
2.给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
反转链表较为简单，下面介绍两种方法：
- 三指针遍历法
给定三个指针prev为NULL，cur = head，next = cur->next，这样往后遍历即可。
typedef struct ListNode ListNode; 法1，三指针往后迭代，prev，cur，next往后，画图才会写 struct ListNode* reverseList(struct ListNode* head) { ListNode*prev = NULL; ListNode*cur = head; while(head) { cur = cur->next; head ->next = prev; prev = head; head = cur; } return prev; }
typedef struct ListNode ListNode; 法2，头插 struct ListNode* reverseList(struct ListNode* head) { ListNode*newhead = NULL; ListNode*cur = head; while(cur) { ListNode*next = cur->next; //头插 cur->next = newhead; newhead = cur; //迭代往后 cur = next; } return newhead; }
3.给定一个头结点为 head 的非空单链表，返回链表的中间点。如果有两个中间结点，则返回第二个中间结点。
只需要使用两个指针，fast和slow指针即可，快指针一次走两步，慢指针一次走一步，这样快指针走完时，慢指针一定走到中间节点。
//最优解：快慢指针，慢指针一次走一步，快指针一次走两步 struct ListNode* middleNode(struct ListNode* head) { struct ListNode*slow = head,*fast = head; while(fast && fast->next) { fast = fast->next->next; slow = slow->next; } return slow; }
4.输入一个链表，输出该链表中倒数第k个结点。
解题思路：仍然使用快慢指针：但是这样的快慢指针不是像上一道题快指针走两步，慢指针走一步。
这里的快慢指针是快指针先走，慢指针后走。
fast先走k步，然后fast和slow同时走。
当fast == NULL时，slow即为倒数第k个
原因：快指针先走的k步，消除了倒数的概念。
typedef struct ListNode ListNode; struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { ListNode*fast = pListHead,*slow = pListHead; int count =0; while(count <k) { if(fast == NULL) { return NULL; } fast = fast ->next; count++; } while(fast) { slow = slow->next; fast = fast->next; } return slow; }
5.将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路：
使用带哨兵位的头节点。2。不使用带哨兵位的头节点
使用带哨兵位的头节点时，好处在于不需要将最小的节点作为头节点，劣势在于由于哨兵位的头节点是malloc出来的，使用完之后需要释放，在释放之间还需要保存哨兵位的头节点的next。
哨兵位的头节点的好处是，不需要再把第一个小的值给head typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { 带哨兵位的头解法： if(list1==NULL) return list2; if(list2 == NULL) return list1; //带哨兵位的头节点 ListNode*head = NULL; head = (ListNode*)malloc(sizeof(ListNode)); ListNode*tail = head; while(list1 && list2) { if(list1->val < list2->val) { tail->next = list1; tail = list1; list1 = list1->next; } else { tail->next = list2; tail = list2; list2 = list2->next; } } if(list1) { tail->next = list1; } if(list2) { tail->next = list2; } //注意这里，不能用prevhead = head，然后return prevhead->next //因为prev = head，head已经free了，相当于prev非法访问了。 //所以只能prev = head->next,return prev; ListNode*prevhead = head->next; free(head); return prevhead; }
6.现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
举个简单的例子：
上面的链表是原链表，定值x是4，也就是小于4的节点需要在前面，大于4的节点在后面，并且不能改变原来链表的节点的顺序。下面的链表即为题目要求的链表。
注意：
由于原链表中的6的next仍然指向2，会造成出现环形链表的情况，会造成死循环，所以需要将6的next 置为NULL。
思路：将小于定值x和大于定值x的链表分开，分别连接后，最后在将小的链表和大的链表连接起来。
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode*LessHead ,*LessTail,*GreaterHead,*GreaterTail; LessHead=LessTail=GreaterHead=GreaterTail= NULL; LessTail = LessHead= (struct ListNode*)malloc(sizeof(struct ListNode)); GreaterTail= GreaterHead = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* cur = pHead; while (cur) { if (cur->val < x) { LessTail->next = cur; LessTail = cur; } else { GreaterTail->next = cur; GreaterTail = cur; } cur = cur ->next; } //到这里说明cur走完链表了，此时需要将两个链表连接起来 LessTail->next = GreaterHead->next; //注意：一定要将GreaterTail->next = NULL //假如链表为2->3->5->7->6->2,GreaterTail->next还指向2 //造成链表成环形了，所以要置空 GreaterTail->next = NULL; ListNode* newnode = LessHead->next; free(LessHead); free(GreaterHead); return newnode; } };
7.
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
思路：所谓的回文结构，其实就是判断链表是否对称。
- 先找出链表的中间节点，然后以该中间节点为界，将链表分割。
- 前面的链表称为list1，后面的链表称为list2。
将list2逆置，再将list1和list2的节点逐个判断，如果list1或者list2的节点都相等，那就是回文结构。
//链表回文的思路： // 1、先找出链表的中间节点，(偶数个找第二个中间节点) // 2.中间节点作为新的链表头进行逆置。 // 将新逆置后的链表和原链表的val相比，（因为原链表的某些节点的next存储着新链表的某些节点的地址） ListNode* MidListNode(ListNode* A) { ListNode*slow =A,*fast = A; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } ListNode* reverseListNode(ListNode* mid) { ListNode*prev = NULL; ListNode*cur = mid; while(cur) { ListNode*pnext = cur->next; cur->next = prev; prev = cur; //迭代往后 cur = pnext; } return prev; } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code heretypedef struct ListNode ListNode; // write code here ListNode*mid = MidListNode(A); ListNode*rhead = reverseListNode(mid); ListNode*curA = A; ListNode*curR = rhead; while(curA && curR) { if(curA->val!=curR->val) { return false; } else { curA = curA->next; curR = curR->next; } } return true; } };
8.给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null
思路：给定一个fast指针和slow指针，先分别遍历两个链表，记录长度，让fast指针指向长链表，fast指针先走 长链表长度-链表长度，随后slow指针从短链表的头开始，和fast链表一起往后走，每个指针一次走一步，如果相等，则相等的点为相交点。
原因：快指针先走的长度差消除了长短链表的长度差。
typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode*curA = headA; ListNode*curB = headB; int i = 0; int j = 0; //先记录两个链表的长度，随后让长链表先走k步，再一起走，就消除了长度差，时间复杂度为O(N),空间复杂度为O(1); //还可以再遍历完两个链表的同时，记录两个链表的尾结点，如果尾结点不相同，那肯定不相交，直接返回NULL ListNode*TailA = NULL; ListNode*TailB = NULL; while(curA) { ++i; TailA = curA; curA = curA->next; } while(curB) { ++j; TailB = curB; curB = curB->next; } if(TailA !=TailB) { return NULL; } if(i>j) { int k = i-j; curA = headA; curB = headB; while(k--) { curA = curA->next;//长链表先走k步 } while(curB && curA) { if(curA == curB) { return curA; } else { curA = curA->next; curB = curB->next; } } } else { int k = j-i; curA = headA; curB = headB; while(k--) { curB = curB->next;//长链表先走k步 } while(curB && curA) { if(curA == curB) { return curA; } else { curA = curA->next; curB = curB->next; } } } return NULL; }
