链表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，循环停止，慢指针的位置就是中间节点的位置·。

我们来测试一下：