04ds_链表面试题

# 移出链表元素
给你一个无头单向不循环链表的首结点l和一个整数 val ，请你删除链表中所有等于 val 的节点，并返回新的首结点 。
/*
struct llist_node
{
	int val;
	struct llist_node *next;
};
*/
struct llist_node* removeElements(struct llist_node* l, int val)
{
    struct llist_node* cur = l;//指向要删除的结点
    struct llist_node* back = NULL;//指向要删除的结点的前一个位置
    
    while(cur != NULL)//判断是否遍历完所有结点
    {
        if(cur->val == val)//判断当前指向的结点是否是要删除的结点
        {
            if(back == NULL)//判断删除的是否是链表的首结点
            {
	l = cur->next;//让l指针指向下一个结点
                free(cur);//释放首结点
                cur = l;//让cur指针指向新的首结点
            }
            else//如果删除的不是首结点就按照普通的删除方法进行
            {
                back->next = cur->next;
                free(cur);
                cur = back->next;
            }
        }
        else//如果不是要删除的结点，找下一个结点
        {
            back = cur;
            cur = cur->next;
        }
    }
    return l;//返回指向首结点的指针l
}

# 反转链表
给你一个无头单向不循环链表的首结点l ，请你反转链表，并返回反转后的链表首结点
/*
struct llist_node
{
	int val;
	struct llist_node *next;
};
*/
struct llist_node* reverseList(struct llist_node* l)
{
	struct llist_node *cur = l;//cur指针指向当前操作的结点
	struct llist_node *p = NULL;//p指针指向原链表中cur的下一个位置
	struct llist_node *next = NULL;//next指针指向反转链表后cur的下一个位置
	
	while(cur != NULL)//判断是否遍历完整个链表
	{
		p = cur->next;//p指针指向原链表中cur的下一个位置
		cur->next = next;//让cur指针指向的结点的next指向前一个位置
		next = cur;//移动next
		cur = p;//移动cur
	}
	return next;
}

# 链表的中间结点
给定一个头结点为handler的单向不循环链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
/*
struct llist_node
{
	int val;
	struct llist_node *next;
};
*/
//快慢指针
//慢指针一次走一步，慢指针一次走两步
struct llist_node* middleNode(struct llist_node* handler)
{
	struct llist_node *s = handler;//慢指针
	struct llist_node *f = handler;//快指针
	
	while(f != NULL && f->next != NULL)
	{
		s = s->next;
		f = f->next->next;
	}
	return s;
}

# 链表中倒数第k个结点
给定一个头结点为handler的单向不循环链表，输出该链表中倒数第k个结点。
/*
struct llist_node
{
	int val;
	struct llist_node *next;
};
*/
//先让一个指针走k个结点，再让另外一个指针跟着走
struct llist_node* FindKthToTail(struct llist_node* handler, int k)
{
	struct llist_node *s = handler;
	struct llist_node *f = handler;

	while(k--)
	{
		if(f == NULL)//判断k值是否大于链表节点数
			return NULL;
		f = f->next;
	}
	while(f != NULL)
	{
		s = s->next;
		f = f->next;
	}
	return s;
}

# 合并两个有序链表
将两个升序的无头单向不循环链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/*
struct llist_node
{
	int val;
	struct llist_node *next;
};
*/
struct llist_node* mergeTwoLists(struct llist_node* l1, struct llist_node* l2)
{
	struct llist_node *l = NULL;
	struct llist_node *cur = NULL;

	if(l1 == NULL)//判断l1链表是否不存在
		return l2;
	if(l2 == NULL)//判断l2链表是否不存在
		return l1;
	if(l1->val < l2->val)
	{
		l = cur = l1;
		l1 = l1->next;
	}
	else
	{
		l = cur = l2;
		l2 = l2->next;
	}
	while(l1 != NULL && l2 != NULL)
	{
		if(l1->val < l2->val)
		{
			cur->next = l1;
			l1 = l1->next;
		}
		else
		{
			cur->next = l2;
			l2 = l2->next;
		}
		cur = cur->next;
	}
	if(l1 == NULL)
		cur->next = l2;
	else
		cur->next = l1;
	return l;
}

# 链表分割
现有一无头单向不循环链表的首结点指针l，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
/*
struct llist_node
{
	int val;
	struct llist_node *next;
};
*/
struct llist_node* partition(struct llist_node* l, int x)
{
	struct llist_node *cur = l;
	struct llist_node *minhead = NULL;
	struct llist_node *maxhead = NULL;
	struct llist_node *mincur = NULL;
	struct llist_node *maxcur = NULL;

	minhead = malloc(sizeof(struct llist_node));
	maxhead = malloc(sizeof(struct llist_node));
	minhead->next = maxhead->next = NULL;
	mincur = minhead;
	maxcur = maxhead;

	while(cur != NULL)
	{
		if(cur->val < x)
		{
			mincur->next  = cur;
			mincur = mincur->next;
		}
		else
		{
			maxcur->next = cur;
			maxcur = maxcur->next;
		}
		cur = cur->next;
	}
	mincur->next = maxhead->next;
	maxcur->next = NULL;
	l = minhead->next;
	free(minhead);
	free(maxhead);
	return l;
}

# 链表的回文结构
`现有一无头单向不循环链表的首结点指针l，请返回一个bool值，代表其是否为回文结构。`

# 环形链表
`给你一个单向链表的头结点 head ，判断链表中是否有环。`

# 单向不循环链表的排序
/*
struct llist_node
{
	int val;
	struct llist_node *next;
};
*/
struct llist_node *pop_sort(struct llist_node *l)

    struct llist_node *p, *q, *tail;
    tail = NULL;
    while((l->next->next) != tail)
    {
        p = l;
        q = l->next;
        while(q->next != tail)
        {
            if((q->val) > (q->next->val))
            {
                p->next = q->next;
                q->next = q->next->next;
                p->next->next = q;
                q = p->next;
            }
            q = q->next;
            p = p->next;
        }
        tail = q;
    }
}