链表的创建与翻转函数以及删除值为key的元素函数

#include<iostream>
using namespace std;
//声明结构体
struct ListNode
{
 int val;
 ListNode * next;
 ListNode(int x) : val(x), next(NULL){}
};
//链表创建函数
ListNode * CreatLinkedList(int a[], int n)
{
 if (n == 0)  return NULL;
 
 ListNode *head = new ListNode(a[0]);
 ListNode *cur=head;
 for (int i = 1; i < n; i++)
 {
  cur->next = new ListNode(a[i]);
  cur = cur->next;
 }
 return head;
}
//链表打印函数
void printLinkedList(ListNode *head)
{
 while (head != NULL)
 {
  cout << head->val << " -> ";
  head = head->next;
 }
 cout << "NULL" << endl;
}
//链表翻转函数
ListNode * reverseLinkedList(ListNode * head)
{
 ListNode *pre = NULL;
 ListNode *cur = head;
 while (cur != NULL)
 {
  ListNode *next = cur->next;//记录下一个指针的位置
  cur->next = pre;           //当前指针指向前一个指针
  pre = cur;               
  cur = next;
 }
 return pre;
}
//删除链表函数
void deleteLinkedList(ListNode *head)
{
 ListNode* cur = head;
 while (cur != NULL)
 {
  ListNode* delcur = cur;
  cur = cur->next;
  delete delcur;
 }
}
int main()
{
 int a[] = { 1, 2, 3, 4, 5, 6 };
 int n = sizeof(a) / sizeof(a[0]);
 ListNode *head = CreatLinkedList(a, n);
 printLinkedList(head);
 ListNode *head2=reverseLinkedList(head);
 printLinkedList(head2);
 deleteLinkedList(head);
 return 0;
}
运行如下:
//在链表中删除key值的元素
ListNode * removeElements(ListNode * head,int key)
{
 ListNode* dummyHead = new ListNode(0);//设立一个虚拟头结点,更方便处理头结点为key的值
 dummyHead->next = head;
 ListNode* cur = dummyHead;
 
 while (cur->next != NULL)
 {
  if (cur->next->val == key)
  {
   ListNode* delcur = cur->next;
   cur->next = delcur->next;
   delete delcur;
  }
  else
   cur = cur->next;
 }
 ListNode *retNode = dummyHead->next;
 delete dummyHead;
 return retNode;
}
删除值为5的元素,运行如下:
//删除链表中倒数第n个元素
ListNode * removeNthFromEnd(ListNode * head, int n)
{
 assert( n >0);
 ListNode* dummyhead = new ListNode(0);
 dummyhead->next = head;
 ListNode *p = dummyhead;
 ListNode *q = dummyhead;
 for (int i = 0; i <n+1; i++)
 {
  assert(q);
  q = q->next;
 }
 while (q)  //while (q!=NULL)
 {
  p = p->next;
  q = q->next;
 }
 ListNode *delnode = p->next;
 p->next = delnode->next;
 delete delnode;
 ListNode * retnode = dummyhead->next;
 delete dummyhead;
 return retnode;
}