面试题 02.04 分割链表

• 定义lesshead和greaterhead链接小于和大于等于k的值
• 分别设置哨兵位和尾节点指针
• 最后将两表去除哨兵位再链接

struct ListNode* partition(struct ListNode* head, int x)
{
	struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
	lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
	lesstail->next = NULL;

	greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
	greatertail->next = NULL;

	struct ListNode* cur = head;
	while (cur)
	{
		if (cur->val < x)
		{
			lesstail->next = cur;
			lesstail = cur;
		}
		else
		{
			greatertail->next = cur;
			greatertail = cur;
		}
		cur = cur->next;
	}
	lesstail->next = greaterhead->next;
	greatertail->next = NULL;

	struct ListNode* newhead = lesshead->next;

	free(lesshead);
	free(greaterhead);
	return newhead;
}

剑指 Offer II 027 回文链表

• 先找到链表中间节点
• 将中间节点以后的节点从原链表截断逆置生成新链表
• 与原链表逐节点的值相比较
  

//回文结构
bool isPalindrome(struct ListNode* head) {
	if (head == NULL)
	{
		return false;
	}

	//找中间节点
	struct ListNode* cur = head, * slow = head, * fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	struct ListNode* mid = slow;

	//将中间节点之后的顺序反转
	struct ListNode* newhead = slow;
	cur = newhead;
	struct ListNode* prev = NULL;
	while (cur)
	{
		struct ListNode* next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	newhead = prev;

	//遍历两组链表，检查是否每位相等
	struct ListNode* cur2 = newhead;
	struct ListNode* cur1 = head;
	while (cur1 && cur2)
	{
		if (cur1->val != cur2->val)
		{
			return false;
		}
		cur1 = cur1->next;
		cur2 = cur2->next;
	}
	return true;
}

160 相交链表

• 根据两链表长度求出长度差k
• 较长的链表先走k步
• 两表再一起走，节点地址相同时返回此节点

 int ListSize(struct ListNode * head)
 {
     struct ListNode * cur=head;
     int len=0;
     while(cur)
    {
        len++;
        cur=cur->next;
    }
    return len;
 }
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int len1=ListSize(headA);
    int len2=ListSize(headB);
    int k=abs(len1-len2);
    struct ListNode * longlist=headA;
    struct ListNode * shortlist=headB;
    if(len1<len2)
    {
        longlist=headB;
        shortlist=headA;
    }
    struct ListNode * cur1=longlist, *cur2=shortlist;
    while(k--)
    {
        cur1=cur1->next;
    }
    while(cur1 && cur2)
    {
        if(cur1==cur2)
        {
            return cur1;
        }
        cur1=cur1->next;
        cur2=cur2->next;
    }
    return NULL;
}

141 环形链表

快慢指针法，相遇则为环形链表

//环形链表，快慢指针法
bool hasCycle(struct ListNode* head) {
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast && fast->next)
	{

		fast = fast->next->next;
		slow = slow->next;
		if (slow == fast)
		{
			return true;
		}
	}
	return false;
}

142 环形链表 II

• 先找到入环点
• 相遇点到入环点的距离等于链头到入环点的距离
• 从链头和相遇点出发，相遇点即为入环点

//环形链表 II
//找到入环点，再判断环形链表代码块内续写
struct ListNode* detectCycle(struct ListNode* head) {
	struct ListNode* slow = head, * fast = head, * meet = NULL;
	while (fast && fast->next)
	{
		//找到快慢指针相遇点
		fast = fast->next->next;
		slow = slow->next;
		//相遇点到入环点的距离等于链头到入环点的距离
		if (slow == fast)
		{
			meet = slow;
			while (meet != head)
			{
				meet = meet->next;
				head = head->next;
			}
			return meet;
		}
	}
	return NULL;
}

138 复制带随机指针的链表

• 在原链表每个节点后复制一个节点
• 根据原节点设置复制节点的random
  • 注意不可复制节点的同时处理random，因为random指向位置还未完成复制
• 将处理好的复制节点链接到newhead
  

//复制带随机指针的链表
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;
	}
	cur = head;
	struct Node* next = NULL;
	//根据原节点设置复制节点的random
	while (cur)
	{
		struct Node* copy = cur->next;
		next = copy->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}
		cur = next;
	}
	//将处理好的复制节点链接到newhead
	cur = head;
	struct Node* newtail = NULL, * newhead = NULL;
	while (cur)
	{
		struct Node* copy = cur->next;
		next = copy->next;
		if (newtail == NULL)
		{
			newhead = newtail = copy;
		}
		else
		{
			newtail->next = copy;
			newtail = copy;
		}
		cur->next = next;
		cur = next;
	}
	return newhead;
}