链表oj测试题（上）

链表的申明：

struct ListNode
{
	int val;
	struct ListNode* next;
};

1.题1

删除指定元素例如：链表1 2 6 3 4 5 6，然后选择删除元素6，返回的链表为1 2 3 4 5 。

代码演示：

typedef struct ListNode ListNode;
 ListNode* removeElements(ListNode* head, int val)
{
	 ListNode* newHead, * newTail;
	 newHead = newTail = NULL;
	 ListNode* pcur = head;
	 while (pcur)
	 {
		 if (pcur->val != val)//不是val就插入新链表
		 {
			 if (newHead == NULL)
			 {
				 newHead = newTail = pcur;//空链表就将头节点和尾节点都指向pcur
			 }
			 else//链表不为空
			 {
				 newTail->next = pcur;
				 newTail = newTail->next;
			 }
          
		 }
		 pcur = pcur->next;

	 }
	 if (newTail)//判断最后的尾节点是否为NULL，如果为NULL的话就为对其去指针域就会报错
	 {
		 newTail->next = NULL;
	 }
	 return newHead;
}

在这里的思路就是遍历原链表碰到不为val的数就尾插到新创建的链表，最后将新链表的头返回来，大家也可以试试将它们的上一个节点的地址保存val下一个节点的地址，然后再将val的空间释放掉，这个方法虽然有些麻烦，但是大家可以练习一下思维。

在这里我们我们要用到尾插的代码，和创建节点才能创建好链表，虽然可以不包装成函数，但是如果将其包装成函数的话可以减少下次需要使用到它的时候，减轻代码量。

尾插：

void InsertBack(ListNode**phead,int val)
{
 assert(phead);
 ListNode* newNode = GetNode(val);
 if (*phead == NULL)
 {
	 *phead = newNode;
	 return;
 }

 ListNode* ptail = *phead;
 while (ptail->next)
 {
	 ptail = ptail->next;
 }
 ptail ->next= newNode;
}

创建节点：

ListNode* GetNode(int val)
{
 ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
 assert(newNode);
 newNode->val = val;
 newNode->next = NULL;
 return newNode;
}

我们可以测试一下代码是否可以达到预想效果：

2.题2

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

代码演示：

ListNode* middleNode(ListNode* phead)
{
 ListNode* slow, * fast;
 slow = fast = phead;
 while (fast && fast->next)//当fast或者fast->next其中一个为空就跳出循环，此时slow刚好指向中节点。
 {//判断式的顺序不能替换，因为当fast为空时，结果fast->在前面这就导致了对空指针的引用，会报错。
	 slow = slow->next;//每次走一步
	 fast = fast->next->next;//每次走两步
 }
 return slow;
}

我们在这里用到的是快慢指针法，这个方法就是创建两个指针变量，然后快指针一次走两步，慢指针一次走一步，当快指针为NULL,或者慢指针next为NULL，循环停止，慢指针的位置就是中间节点的位置·。

我们来测试一下：