选做旅游网站的课题分析,武昌网站建设制作,国外网站推荐,商城门户网站源码一、链表的回文结构 思路#xff1a; 找到链表的中间节点#xff0c;然后逆置链表的后半部分#xff0c;再一一遍历链表的前半部分和后半部分#xff0c;判断是是否为回文结构。 快慢指针找到链表的中间节点 slow指针指向的就是中间节点 逆置链表后半部分 逆置链表后半部分…一、链表的回文结构 思路 找到链表的中间节点然后逆置链表的后半部分再一一遍历链表的前半部分和后半部分判断是是否为回文结构。 快慢指针找到链表的中间节点 slow指针指向的就是中间节点 逆置链表后半部分 逆置链表后半部分 遍历链表前半部分和后半部分 如果left和right指向的数据不相等就跳出循环返回false如果遍历到left或者right为NULL数据都相等那么链表具有回文结构返回true。 这里如果是奇数个节点
遍历结束后
class PalindromeList {
public://找链表中间节点ListNode* Listmid(ListNode* phead){ListNode* fast, *slow;fastslowphead;while(fast fast-next){slowslow-next;fastfast-next;}return slow;}//逆置ListNode* reverse(ListNode* phead){ListNode* l1,*l2,*l3;l1NULL;l2phead;while(l2){l3l2-next;l2-nextl1;l1l2;l2l3;}return l1;}bool chkPalindrome(ListNode* A) {// write code here//找到链表中间节点ListNode* midListmid(A);//逆置后半部分ListNode* phead reverse(mid);//比较ListNode* left, *right;leftA;rightphead;while(right left){if(right-val!left-val){return false;}leftleft-next;rightright-next;}return true;}
};
二、相交链表 判断两个链表是否相交如果相交就返回相交节点如果链表不相交那就返回NULL
思路 先遍历两个链表记录两个链表的节点个数再同时遍历两个链表 让节点个数多的链表先往前走s链表的节点个数差同时遍历两个链表如果指向链表的指针相等就返回当前节点如果遍历链表结束后都没有相等的节点那就返回NULL。 typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA,struct ListNode* headB) {if (headA NULL) {return NULL;}if (headB NULL) {return NULL;}int sizeA 0, sizeB 0;ListNode *l1, *l2;l1 headA;l2 headB;while (l1) {sizeA;l1 l1-next;}while (l2) {sizeB;l2 l2-next;}ListNode* shortList headA;ListNode* longList headB;int s abs(sizeA - sizeB);if (sizeA sizeB) {shortList headB;longList headA;}while (s) {s--;longList longList-next;}while (longList shortList) {if (longList shortList) {return longList;}longList longList-next;shortList shortList-next;}return NULL;
}
三、环形链表1 判断 链表中是否存在环如果存在就返回true如果不存在就返回false
思路快慢指针 定义两个指针fast和slow遍历链表fast每次向前走两步slow每次向前走一步如果链表存在环fast与slow指针一定会相遇如果遍历链表fast或者fast-next为NULL则链表不存在环。 根据题目所给示例来分析一下 首先定义两个指针 fast slow fast向前走两步slow向前走一步 fast向前走两步slow向前走一步 fast向前走两步slow向前走一步 此时fast和slow相遇证明链表中存在环返回true。 如果链表不存在环结构遍历过程中fast或者fast-next指针会等于NULL将这个作为结束条件即可。
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* fast, *slow;fastslowhead;while(fast fast-next){fastfast-next-next;slowslow-next;if(slow fast){return true;}}return false;
}
四、环形链表2 上面只是让我们判断链表是否带环这道题让我们返回链表环的起始节点如果不存在环就返回NULL。
思路 使用快慢指针找到快慢指针的相遇节点再定义两个指针从相遇节点和链表头结点开始遍历两个指针相遇时的节点就是链表环的起始节点。 根据题目的示例来分析 先找到链表快慢指针的相遇节点 定义两个指针从链表头部和相遇节点开始遍历链表 遍历链表直到两个指针相遇 两个指针相遇此时指针指向的节点就是链表环的起始节点。
typedef struct ListNode ListNode;
ListNode* hasCycle(struct ListNode *head) {ListNode* fast, *slow;fastslowhead;while(fast fast-next){fastfast-next-next;slowslow-next;if(slow fast){return slow;}}return NULL;
}
struct ListNode *detectCycle(struct ListNode *head) {//找到快慢指针相遇节点ListNode* poshasCycle(head);if(posNULL){return NULL;}//从头结点和相遇节点开始遍历ListNode* ptailhead;while(1){if(posptail){return pos;}pospos-next;ptailptail-next;}
}
五、随机链表的复制 这里题目上提到了一个深拷贝 思路 先在原链表的基础上创建节点形成新的链表再给链表节点的random指针赋值最后断开新链表和原链表的连接即可。 深拷贝原链表 拷贝过后 给random指针赋值 断开新链表和原链表之前的连接 这样就深拷贝了原链表返回新链表的头节点即可。
typedef struct Node Node;
// 创建节点
Node* BuyNode(int x) {Node* newnode (Node*)malloc(sizeof(Node));newnode-next newnode-random NULL;newnode-val x;return newnode;
}
// 深拷贝
void CopyList(Node** head) {Node* ptail *head;Node* next NULL;while (ptail) {next ptail-next;Node* newnode BuyNode(ptail-val);newnode-next next;ptail-next newnode;ptail next;}
}
void Connect(Node** head) {Node* ptail *head;Node* copy (*head)-next;while (ptail) {copy ptail-next;if (ptail-random)copy-random ptail-random-next;ptail copy-next;}
}
struct Node* copyRandomList(struct Node* head) {if (head NULL){return NULL;} // 深拷贝原链表CopyList(head);// 连接random指针Connect(head);// 断开链表Node* ptail head;Node* newhead head-next;Node* copy head-next;while (ptail-next-next) {ptailcopy-next;copy-next copy-next-next;copy copy-next;}return newhead;
}
