-
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 hereListNode* 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 指针置为NULLlesstail->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 hereListNode* 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、从原链表和反链表比较结点的值