目录
1.面试题 02.02. 返回倒数第 k 个节点
2.OR36 链表的回文结构
3.160. 相交链表
1.面试题 02.02. 返回倒数第 k 个节点
思路：快慢指针，快指针先走k格，慢指针同步
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k){struct ListNode* fast,*slow;fast=slow=head;while(k--){fast=fast->next;}while(fast){fast=fast->next;slow=slow->next;}return slow->val;
}
2.OR36 链表的回文结构
思路：先找中间节点，然后将节点后逆置，最后一一比较
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow=head,*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;}struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur=head;struct ListNode* newhead=NULL;while(cur){struct ListNode*next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;}bool chkPalindrome(ListNode* A) {struct ListNode* mid=middleNode(A);struct ListNode* rmid=reverseList(mid);while(rmid&&A){if(rmid->val!=A->val)return false;rmid=rmid->next;A=A->next;}return true;}
};3.160. 相交链表
思路：先判断是否相交，再计算长度差值，再一一比较
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* cura=headA,*curb=headB;int lena=1,lenb=1;while(cura->next){cura=cura->next;lena++;}while(curb->next){curb=curb->next;lenb++;}if(cura!=curb){return NULL;}int gap=abs(lena-lenb);struct ListNode* long1=headA,*short1=headB;if(lenb>lena){long1=headB;short1=headA;}while(gap--){long1=long1->next;}while(long1!=short1){long1=long1->next;short1=short1->next;}return long1;
}4.142. 环形链表 II
思路一：
证明：
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow,*fast;slow=fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){struct ListNode* meet=slow;while(meet!=head){meet=meet->next;head=head->next;}return meet;}}return NULL;
}思路二：改为相交链表
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* slow, * fast;slow = fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next;if (slow == fast){struct ListNode* meet = slow;struct ListNode* newhead = meet->next;meet->next = NULL;return getIntersectionNode(head, newhead);//相交链表}}return NULL:
}5.138. 随机链表的复制
思路：
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node *cur=head;//新建的节点插入在原节点的后面while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}//randomcur=head;while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}//摘取struct Node* copyhead=NULL,*copytail=NULL;cur=head;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(copytail==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}cur=next;}return copyhead;
}