總結(jié)

最近面了百度跟騰訊的c++開發(fā)，之前對(duì)數(shù)據(jù)結(jié)構(gòu)只是局限在用上，當(dāng)時(shí)涉及到基礎(chǔ)的應(yīng)用的時(shí)候感覺有點(diǎn)捉襟見肘，整理了下關(guān)于鏈表的題，以及基礎(chǔ)的鏈表類的操作。感覺面試官對(duì)鏈表情有獨(dú)鐘，特別是一些普通的數(shù)組的題讓你用鏈表實(shí)現(xiàn)，就比較惡心。。

首先是關(guān)于鏈表的基本操作

下面是一個(gè)關(guān)于鏈表類基礎(chǔ)的操作

//鏈表的操作集合，記面試失敗的第二次，好好準(zhǔn)備

#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;
//鏈表類，實(shí)現(xiàn)鏈表的所有操作
class LinkList{
public:
    LinkList();                      //構(gòu)建一個(gè)單鏈表;
    ~LinkList();                  //銷毀一個(gè)單鏈表;
    void CreateLinkList(int n);   //創(chuàng)建一個(gè)單鏈表
    void TravalLinkList();        //遍歷線性表
    int GetLength();              //獲取線性表長(zhǎng)度
    bool IsEmpty();               //判斷單鏈表是否為空
    struct ElemType * Find(DataType data); //查找節(jié)點(diǎn)
    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;
}
// 創(chuàng)建鏈表
void LinkList::CreateLinkList(int n) {
    struct ElemType *pnew, *ptemp;
    ptemp=head;
    if(n<0)
        cout<<"輸入節(jié)點(diǎn)是錯(cuò)誤的";
    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;
}
//查找鏈表的節(jié)點(diǎn)
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;          //創(chuàng)建一個(gè)指針指向頭結(jié)點(diǎn)
    struct ElemType *ptemp = NULL;      //創(chuàng)建一個(gè)占位節(jié)點(diǎn)
    if (p->next == NULL) {        //判斷鏈表是否為空
        cout << "單鏈表空" << endl;
    } else {
        while (p->next != NULL)   //循環(huán)到尾部的前一個(gè)
        {
            ptemp = p;            //將ptemp指向尾部的前一個(gè)節(jié)點(diǎn)
            p = p->next;          //p指向最后一個(gè)節(jié)點(diǎn)
        }
        delete p;                //刪除尾部節(jié)點(diǎn)
        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;
        }
    }
}
//獲取鏈表的長(zhǎng)度
int LinkList::GetLength() {
    int count=0;
    struct ElemType *p=head;
    while(p!=NULL) {
        count++;
        p = p->next;
    }
    return(count);

}

第二部分是關(guān)于鏈表的題目

1.實(shí)現(xiàn)鏈表的反轉(zhuǎn)，主要有兩種思路，一種是遍歷到最后，然后慢慢就行交換，需要兩個(gè)指針。第二種的話就是利用頭插法實(shí)現(xiàn)對(duì)鏈表的反轉(zhuǎn)。關(guān)于鏈表反轉(zhuǎn)的題目，其實(shí)很常見，其實(shí)就是鏈表的回文串，因?yàn)槭擎湵?，沒法索引，關(guān)于中心的方式肯定是不行的，所以這個(gè)地方就需要反轉(zhuǎn)來實(shí)現(xiàn)。實(shí)現(xiàn)方法如下

#include<iostream>
using namespace std;

//定義一個(gè)鏈表節(jié)點(diǎn)
struct ListNode
{
  int value;
  ListNode *next;
};

//插入一個(gè)新節(jié)點(diǎn)到鏈表中(放在鏈表頭部)
void CreateList(ListNode * & head, int data)
{
  //創(chuàng)建新節(jié)點(diǎn)
  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;
}


//遞歸方式：實(shí)現(xiàn)單鏈表反轉(zhuǎn)
ListNode * ReverseList(ListNode * head)
{
  //遞歸終止條件：找到鏈表最后一個(gè)結(jié)點(diǎn)
  if (head == NULL || head->next == NULL)
      return head;
  else
  {
      ListNode * newhead = ReverseList(head->next);//先反轉(zhuǎn)后面的鏈表，從最后面的兩個(gè)結(jié)點(diǎn)開始反轉(zhuǎn)，依次向前
      head->next->next = head;//將后一個(gè)鏈表結(jié)點(diǎn)指向前一個(gè)結(jié)點(diǎn)
      head->next = NULL;//將原鏈表中前一個(gè)結(jié)點(diǎn)指向后一個(gè)結(jié)點(diǎn)的指向關(guān)系斷開
      return newhead;
  }
}
//頭插法實(shí)現(xiàn)反轉(zhuǎn)
ListNode * ReverseListIn(ListNode * head)
{
  ListNode *q,*p;
  p=head;
  head=NULL;
  while(p){
      q = p->next;  //q指向剩余鏈表的首個(gè)節(jié)點(diǎn)
      //用頭插法將節(jié)點(diǎn)插入到新的逆轉(zhuǎn)鏈表
      p->next = head;
      head = p;
      p = q;

  }
  return head;
}


//非遞歸方式：實(shí)現(xiàn)單鏈表反轉(zhuǎn)
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作為中間節(jié)點(diǎn)，記錄當(dāng)前結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的位置
      cur->next = prev;  //當(dāng)前結(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)
      prev = cur;     //指針后移
      cur = temp;  //指針后移，處理下一個(gè)節(jié)點(diǎn)
  }

  head->next = NULL; //while結(jié)束后，將翻轉(zhuǎn)后的最后一個(gè)節(jié)點(diǎn)（即翻轉(zhuǎn)前的第一個(gè)結(jié)點(diǎn)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;
}