链表常见题目
1.删除链表中给定值val的值(这个题最好能自己完全写出来)(该题耗时半个多小时)
输入:1->2->6->3->4->5->6, val = 6
输出:1->2->3->4->5
/*
Definition for singly_linked list.
struct ListNode{
int val;
struct ListNode* next;//结构体指针
}
*/
struct ListNode* remoceElements(struct listNode* head, int val){
struct ListNode* prev = NULL, *cur = head;
while (cur){
if (cur->val == val){
//非头结点
if (prev != NULL){
prev->next = cur->next;
}
else{
//头结点,更新头结点
head = cur->next;
}
LisrNode* next = cur->next;
//删除当前节点
free(cur);
//更新到下一个节点
cur = next;
}
else{
prev = cur;
cur = cur->next;
}
}
return head;
}
2.反转一个单链表
示例:输入:1->2->3->4->5->NULL
输出:NULL->5->4->3->2->1
思路:空链表:元素头插.NULL,1插进去做新的head,依次...
node->next = new head;newhead = node;
/*
Definition for singly_linked list.
struct ListNode{
int val;
struct ListNode* next;
}
*/
struct ListNode* reversrList(struct ListNode* head){
struct ListNode* newHead = NULL;
struct ListNode* cur = head;
while (cur){
//保存下一个节点的位置
struct ListNode* next = cur->next;
//头插
cur->next = newHead;
newHead = cur;
//头插下一个数据
cur = next;
}
return newHead;
}
3.给定一个带有头结点head的非空单链表,返回链表的中间节点.如果有两个中间节点,则返回第二个中间节点.
思路:不使用遍历两次的方法,使用快慢指针(一个指针一次走两步,一个指针一次走一步)
/*
Definition for singly_linked list.
struct ListNode{
int val;
struct ListNode* next;
}
*/
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->nest){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
4.输入一个链表,输出该链表中倒数第k个节点
思路:依然不使用循环在输出(n-k),还是用两个指针,让一个先走k次再同时走输出走的比较少的.
struct ListNode* FindkthToTail(struct ListNode* pListHead, int k){
struct ListNode* fast, *slow;
fast = slow = pListHead;
while (k--){
if (fast)
fast = fast->nest;
else
return NULL;
}
while (fast){
fast = fast->nest;
slow = slow->nest;
}
return slow;
}
5.将两个有序链表合并为一个新的有序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的.
示例:输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
struct ListNode* mergeTowLists(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL)
return l2;
if (l2 == NULL)
return l1;
struct ListNode* newHead, *newTail;
//确定表头
if (l1->val <= l2->val){
newHead = newTail = l1;
l1 = l1->nest;
}
else{
newHead = newTail = l2;
l2 = l2->nest;
}
//合并,新的节点插入表尾
while (l1 && l2){
if (l1->val <= l2->val){
newTail->next = l1;
l1 = l1->next;
newTail = newTail->next;
}
else{
newTail->next = l2;
l2 = l2->next;
newTail = newTail->next;
}
}
//合并剩余的节点
if (l1)
newTail->next = l1;
if (l2)
newTail->next = l2;
return newHead;
}
6.编写代码,以给定值x为基准将链表分割成两部分,所有小于x的节点排在大于或等于x的节点之前.
ListNode* partition(ListNode* pHead, int x){
struct ListNode* lessHead, *lessTail, *greaterHead, *greaterTail, *cur;
lessHead = lessTail = greaterHead = greaterTail = NULL;
cur = pHead;
while (cur){
if (cur->val < x){
//判断是否为空链表
if (lessHead == NULL)
lessHead = lessTail = cur;
else{
lessTail->nest = cur;
lessTail = lessTail->next;
}
}
else{
if (greaterHead == NULL)
greaterHead = greatTail = cur;
else{
greaterTail->next = cur;
greaterTail = greaterTail->next;
}
}
cur = cur->next;
}
}
//链接两个链表
if (lessTail)
lessTail->next = greatHead;
if (greaterTail)
greaterTail->next = NULL;
if (lessHead)
return lessHead;
else
return greaterHead;
