阅读量:0
1.删除链表中等于给定值 val 的所有节点。 OJ链接
typedef struct ListNode ListNode; struct ListNode { int val; struct ListNode* next; }; struct ListNode* removeElements(struct ListNode* head, int val) { //创建新链表 ListNode* newhead, *newtail; newhead = newtail = NULL; //遍历原链表 ListNode* pcur = head; while (pcur) { if (pcur->val != val) //遍历原链表，直到遍历至原链表的值与 val 的结点 { if (newhead == NULL) //链表为空 { newhead = newtail = NULL; } else //链表不为空，将原链表的结点尾插到新链表中 { newtail->next = pcur; newtail = newtail->next; } } pcur = pcur->next; } if (newtail) //如果操作完后新的链表不为空，才能 newtail->next = NULL ； { newtail->next = NULL; } return newhead; }- 思路：创建新链表，将原链表中值不为val的结点尾插到新链表
2.反转一个单链表。 OJ链接
struct ListNode* reverseList(struct ListNode* head) { //处理空链表 if (head == NULL) { return NULL; } //创建三个指针 ListNode* n1, * n2, * n3; n1 = NULL; n2 = head; n3 = n2->next; while (n2) { n2->next = n1; n1 = n2; n2 = n3; if (n3) { n3 = n3->next; } } return n1; }- 思路：创建三个指针，在原链表上就可以修改指针的指向
原链表： 
循环一次后：
以此类推，当 n2 为 NULL 时跳出循环，此时 n1 指向的结点就是链表的新的头结点
（注意：在判断 n3 时要注意他是否已经跳出链表了，因为 n3 是移动的最快的，如果已经跳出链表就不能进行 ->next 操作）
3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接
struct ListNode* middleNode(struct ListNode* head) { ListNode* slow=head, * fast=head; //创建两个指针，快慢指针 while (fast && fast->next) { slow = slow->next; //慢指针每次走一步，快指针每次走两步 fast = fast->next->next; } return slow; //此时慢指针 slow 指向的节点刚好就是中间的结点 }- 思路：快慢指针，慢指针每次走一步，快指针每次走两步
当链表长度为奇数时：
当链表长度为偶数时：
（注意：while 中的（fast && fast->next）顺序不能更改，当 fast 已经为空时，如果改成
（fast->next && fast），条件会先按顺序执行 fast->next ，从而报错）
- 慢指针每次走一步，快指针每次走两步，当快指针走到链表的结尾时，假设链表的长度为 n ，快指针走的路程是慢指针的两倍，此时慢指针走的路程就是 n/2.
4.输入一个链表，输出该链表中倒数第k个结点。 OJ链接
int kthToLast(struct ListNode* head, int k) { ListNode* fast = head,*slow=head; while (k--) { fast = fast->next; } while (fast) { slow = slow->next; fast = fast->next; } return slow->val; }- 思路：创建两个指针，1、先让 fast 向前走K步；
- 2、slow 和 fast 同步前进，fast 到结尾，slow 到目标。
当 fast =NULL
5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { //处理链表为空 if (list1 == NULL) //l1为空时，返回l2 { return list2; } if (list2 == NULL) //l2为空时，返回l1 { return list1; } ListNode* newhead, * newtail; //创建新的链表 newhead = newtail = (ListNode*)malloc(sizeof(ListNode)); //创建一个非空链表，减少了判断链表为空和非空情况导致的代码冗余 ListNode* l1 = list1; //创建两个指针分别指向两个链表的头结点 ListNode* l2 = list2; //进行比较尾插 while (l1 && l2) { if (l1->val < l2->val) { newtail->next = l1; newtail = newtail->next; l1 = l1->next; } else { newtail->next = l2; newtail = newtail->next; l2 = l2->next; } } if (l1) //跳出循环只用两种情况：要么 l1 为空（l2 肯定不为空）；要么 l2 为空（l1 肯定不为空） { newtail->next = l1; } if (l2) { newtail->next = l2; } ListNode* ret = newhead->next; free(newhead); newhead = NULL; return ret; } - 思路：创建新链表，遍历原链表，谁小就尾插到新链表中
6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ链接
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode* lesshead,*lesstail; lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode)); //大链表 ListNode* greathead,*greattail; greathead=greattail=(ListNode*)malloc(sizeof(ListNode)); //小链表 ListNode* pcur =pHead; //遍历链表 while(pcur) { if(pcur->val<x) //当原链表结点的值小于 x，尾插到小链表 { lesstail->next=pcur; lesstail=lesstail->next; } else //当原链表结点的值大于 x，尾插到大链表 { greattail->next=pcur; greattail=greattail->next; } pcur=pcur->next; } greattail->next=NULL; //将大链表的尾结点的 next 指针置为NULL lesstail->next=greathead->next; // 大小链表首尾相连 ListNode* ret= lesshead->next; free(lesshead); free(greathead); lesshead=greathead=NULL; return ret; } };- 思路：创建大链表、小链表，将小于 x 值的结点尾插到对应的链表中，最后小链表的尾与大链表的头相连。
- （注意：不能忘了最后将大链表的 next 指针指向= NULL）
7.链表的回文结构。OJ链接
bool chkPalindrome(ListNode* A) { // write code here ListNode* mid=middleNode(A); //找出原链表的中间结点 ListNode*right=reverseList(mid); //以次中间结点为头结点反转后面的链表 ListNode*left=A; //从原链表和反链表比较结点的值 while(right) { if(left->val!=right->val) { return false; } left=left->next; right=right->next; } return true; }- 思路：1、找出链表的中间结点
- 2、将中间结点之后的链表进行反转
- 3、从原链表和反链表比较结点的值
