总结

最近面了百度跟腾讯的c++开发，之前对数据结构只是局限在用上，当时涉及到基础的应用的时候感觉有点捉襟见肘，整理了下关于链表的题，以及基础的链表类的操作。感觉面试官对链表情有独钟，特别是一些普通的数组的题让你用链表实现，就比较恶心。。

首先是关于链表的基本操作

下面是一个关于链表类基础的操作

//链表的操作集合，记面试失败的第二次，好好准备

#include <list>
#include <vector>
#include <iostream>
using namespace std;
typedef int DataType;
#define LinklistNode ElemType
#define ERROR NULL
struct LinklistNode
{
    int data;
    LinklistNode *next;
}LinklistNode;
//链表类，实现链表的所有操作
class LinkList{
public:
    LinkList();                      //构建一个单链表;
    ~LinkList();                  //销毁一个单链表;
    void CreateLinkList(int n);   //创建一个单链表
    void TravalLinkList();        //遍历线性表
    int GetLength();              //获取线性表长度
    bool IsEmpty();               //判断单链表是否为空
    struct ElemType * Find(DataType data); //查找节点
    void InsertElemAtEnd(DataType data);            //在尾部插入指定的元素
    void InsertElemAtIndex(DataType data,int n);    //在指定位置插入指定元素
    void InsertElemAtHead(DataType data);           //在头部插入指定元素
    void DeleteElemAtEnd();       //在尾部删除元素
    void DeleteElemAtHead();
    struct ElemType * reverseL(struct LinklistNode *head);

private:
    struct LinklistNode *head;
};
LinkList::LinkList(){
head=new struct ElemType;
head->next= nullptr;
head->data=0;
}
LinkList::~LinkList(){
    delete head;
}
// 创建链表
void LinkList::CreateLinkList(int n) {
    struct ElemType *pnew, *ptemp;
    ptemp=head;
    if(n<0)
        cout<<"输入节点是错误的";
    for (int i = 0; i < n; ++i) {
        pnew = new struct ElemType;
        cin>>pnew->data;
        pnew->next = NULL;
        ptemp->next=pnew;
        ptemp=pnew;
    }
}
//判断链表是否空
bool LinkList::IsEmpty() {
    if(head->next== nullptr)
        return true;
    else
        return false;
}
//查找链表的节点
struct ElemType *LinkList::Find(DataType data) {
    struct ElemType *p = head;
    if (p == NULL) {
        cout << 'the list is empty';
        return ERROR;
    } else {
        while (p->next != NULL) {
            if (p->data == data)
                return p;
            p = p->next;
        }
        return NULL;
    }
}
//在头上插入值
void LinkList::InsertElemAtHead(DataType n){
    struct ElemType *tem=new struct ElemType;
    tem->data=n;
    struct ElemType *p=head;
    if(head==NULL)
        head=tem;
    else{
        tem->next=p;
        p=tem;
    }
}
//在尾部插入元素
void LinkList::InsertElemAtEnd(DataType data) {
    struct ElemType *tem=new struct ElemType;
    tem->data=data;
    tem->next=NULL;
    struct ElemType *p=head;
    if(head==NULL)
        head=tem;
    else{
        while(p->next!=NULL){
            p->next=tem;
        }

    }
}

// 在尾部删除元素
void LinkList::DeleteElemAtEnd() {
    struct ElemType *p = head;          //创建一个指针指向头结点
    struct ElemType *ptemp = NULL;      //创建一个占位节点
    if (p->next == NULL) {        //判断链表是否为空
        cout << "单链表空" << endl;
    } else {
        while (p->next != NULL)   //循环到尾部的前一个
        {
            ptemp = p;            //将ptemp指向尾部的前一个节点
            p = p->next;          //p指向最后一个节点
        }
        delete p;                //删除尾部节点
        p = NULL;
        ptemp->next = NULL;
    }
}
//遍历线性表
void LinkList::TravalLinkList() {
    if(head==NULL|| head->next==NULL)
        cout<<"The list is null";
    else{
        struct ElemType *p=head;
        while(head->next!=NULL){
            p=p->next;
            cout<<p->data;
        }
    }
}
//获取链表的长度
int LinkList::GetLength() {
    int count=0;
    struct ElemType *p=head;
    while(p!=NULL) {
        count++;
        p = p->next;
    }
    return(count);

}

第二部分是关于链表的题目

1.实现链表的反转，主要有两种思路，一种是遍历到最后，然后慢慢就行交换，需要两个指针。第二种的话就是利用头插法实现对链表的反转。关于链表反转的题目，其实很常见，其实就是链表的回文串，因为是链表，没法索引，关于中心的方式肯定是不行的，所以这个地方就需要反转来实现。实现方法如下

#include<iostream>
using namespace std;

//定义一个链表节点
struct ListNode
{
  int value;
  ListNode *next;
};

//插入一个新节点到链表中(放在链表头部)
void CreateList(ListNode * & head, int data)
{
  //创建新节点
  ListNode * p = (ListNode*)malloc(sizeof(ListNode));
  p->value = data;
  p->next = NULL;

  if (head == NULL)
  {
      head = p;
      return;
  }
  p->next = head;
  head = p;
}

void  printList(ListNode* head)
{
  ListNode * p = head;
  while (p != NULL)
  {
      cout << p->value<< " ";
      p = p->next;
  }
  cout << endl;
}


//递归方式：实现单链表反转
ListNode * ReverseList(ListNode * head)
{
  //递归终止条件：找到链表最后一个结点
  if (head == NULL || head->next == NULL)
      return head;
  else
  {
      ListNode * newhead = ReverseList(head->next);//先反转后面的链表，从最后面的两个结点开始反转，依次向前
      head->next->next = head;//将后一个链表结点指向前一个结点
      head->next = NULL;//将原链表中前一个结点指向后一个结点的指向关系断开
      return newhead;
  }
}
//头插法实现反转
ListNode * ReverseListIn(ListNode * head)
{
  ListNode *q,*p;
  p=head;
  head=NULL;
  while(p){
      q = p->next;  //q指向剩余链表的首个节点
      //用头插法将节点插入到新的逆转链表
      p->next = head;
      head = p;
      p = q;

  }
  return head;
}


//非递归方式：实现单链表反转
ListNode* reverseList2(ListNode* head) {
  if (head == NULL || head->next == NULL)
      return head;
  ListNode* prev = head;
  ListNode* cur = head->next;
  ListNode* temp = head->next->next;

  while (cur){
      temp = cur->next; //temp作为中间节点，记录当前结点的下一个节点的位置
      cur->next = prev;  //当前结点指向前一个节点
      prev = cur;     //指针后移
      cur = temp;  //指针后移，处理下一个节点
  }

  head->next = NULL; //while结束后，将翻转后的最后一个节点（即翻转前的第一个结点head）的链域置为NULL
  return prev;
}


int main()
{
  ListNode * head = NULL;
  for (int i = 0; i<9; i++)
      CreateList(head, i);
  printList(head);
  head= ReverseListIn(head);
  printList(head);
  return 0;
}