面试题（1）顺序表链表

1.删除链表中等于给定值 val 的所有节点。

https://leetcode-cn.com/problems/remove-linked-list-elements/description/

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { if(head==NULL) return head; struct ListNode *cur=head->next; struct ListNode *prev=head; while(cur) { if(cur->val==val) { prev->next=cur->next; free(cur); cur=prev->next; } else { prev=cur; cur=cur->next; } } if(head->val==val) return head->next; else return head; }

2.反转一个单链表。

https://leetcode-cn.com/problems/reverse-linked-list/description/

创建一个新的结点，重新穿起来

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(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个指针

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode *n1,*n2,*n3; if(head==NULL) return NULL; if(head->next==NULL) return head; n1=head; n2=n1->next; n3=n2->next; n1->next=NULL; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; }

3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

https://leetcode-cn.com/problems/middle-of-the-linked-list/description/

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { struct ListNode *slow,*fast; slow=head; fast=slow; while(fast!=NULL && fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } return slow; }

4.输入一个链表，输出该链表中倒数第k个结点。

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode *slow=pListHead; ListNode *fast=pListHead; unsigned int i=0; for(i=0;i<k;i++) { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; } };

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

https://leetcode-cn.com/problems/merge-two-sorted-lists/description/

创建一个节点连接在它后面

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode *head,*tail; if(l1==NULL) return l2; else if(l2==NULL) return l1; head=(struct ListNode *)malloc(sizeof(struct ListNode)); tail=head; while(l1 && l2) { if(l1->val < l2->val) { tail->next=l1; l1=l1->next; } else { tail->next=l2; l2=l2->next; } tail=tail->next; } tail->next=l1?l1:l2; return head->next; }

找出第一个最小的数最为头结点

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode *head,*tail; if(l1==NULL) return l2; else if(l2==NULL) return l1; if(l1->val<l2->val) { head=l1; l1=l1->next; } else { head=l2; l2=l2->next; } tail=head; while(l1 && l2) { if(l1->val < l2->val) { tail->next=l1; l1=l1->next; } else { tail->next=l2; l2=l2->next; } tail=tail->next; } tail->next=l1?l1:l2; return head; }

6编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

给定一个链表的头指针ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { struct ListNode *less,*lTail; struct ListNode *greater,*gTail; less=(struct ListNode *)malloc(sizeof(struct ListNode)); lTail=less; greater=(struct ListNode *)malloc(sizeof(struct ListNode)); gTail=greater; struct ListNode *cur=pHead; while(cur) { if(cur->val<x) { lTail->next=cur; lTail=lTail->next; } else { gTail->next=cur; gTail=gTail->next; } cur=cur->next; } gTail->next=NULL; lTail->next=greater->next; pHead=less->next; free(less); less=NULL; free(greater); greater=NULL; return pHead; } };

9.编写一个程序，找到两个单链表相交的起始节点。

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/

暴力求解

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *curA,*curB; curA=headA; while(curA) { curB=headB; while(curB) { if(curB==curA) { return curA; } curB=curB->next; } curA=curA->next; } return NULL; }

有效解法

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *curA,*curB; int lenA = 0,lenB = 0; curA=headA; curB=headB; while(curA) { lenA++; curA=curA->next; } while(curB) { lenB++; curB=curB->next; } int gap=abs(lenA-lenB); struct ListNode *longList=(lenA>lenB)?headA:headB; struct ListNode *shortList=(lenA>lenB)?headB:headA; while(gap--) { longList=longList->next; } while(longList&&shortList) { if(longList==shortList) { return longList; } longList=longList->next; shortList=shortList->next; } return NULL; }

10.给定一个链表，判断链表中是否有环。

https://leetcode-cn.com/problems/linked-list-cycle/description/

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode *slow,*fast; slow=head; fast=slow; while(fast!=NULL&& fast->next!=NULL) { slow=slow->next; fast=fast->next->next; if(slow==fast) return true; } return false; }

11.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

https://leetcode-cn.com/problems/linked-list-cycle-ii/description/

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow,*fast; slow=head; fast=slow; while(fast!=NULL&& fast->next!=NULL) { slow=slow->next; fast=fast->next->next; if(slow==fast) { slow=head; while(slow!=fast) { slow=slow->next; fast=fast->next; } return slow; } } return NULL; }