数据结构进阶实训四 链表

Data structure advanced training course notes and algorithm exercises
数据结构进阶实训课程笔记和算法练习

Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining

---

---

题目1

给定一个单链表L，L为头指针，判断该链表内是否局部存在环？

1.1 算法设计思想

使用快慢指针判断单链表是否存在环。

使用slow、fast 2个指针，slow慢指针每次向前走1步，fast快指针每次向前走2步，若存在环的话，必定存在某个时候 slow = fast 快慢指针相遇。

返回值为1：存在环

返回值为0：不存在环

1.2 源代码

typedef struct Node {
  int data;
  struct Node *next;
}Node, *LinkList;

void InitLinkList(LinkList *L) {
  *L = (LinkList)malloc(sizeof(Node));
  (*L)->next = NULL;
  Node *r=*L, *s, *temp;
  int i=0;
  while(i<10){
    s=(Node*)malloc(sizeof(Node));
    s->data=i;
    r->next=s;
    s->next=NULL;
    if(i==4){   // 记住一个元素,以助后面成环
      temp=r;
    }
    r=s;
    i++;
  }
  r->next=temp;   // 成环
}

int IsLoopLinkList(LinkList list){
  //空指针
  if(list == NULL){
    return 0;
  }
  //只有头结点,没有元素
  if(list->next == NULL){
    return 0;
  }
  Node* slow = list;
  Node* fast = list;
  int loc = 0;
  while (1){
    if(fast->next == NULL){
      //快指针 到底链表尾结点说明 没有环，此时slow 指向中间结点
      return 0;
    }
    else{
      if (fast->next != NULL && fast->next->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
      }
      else{
        fast = fast->next;
      }
    }
    //某个时刻 快慢指针相遇，说明此处存在环！
    if(slow == fast){
      return 1;
    }
  }
  return 0;
}

1.3 运行情况截图

---

---

题目2

找到单链表中倒数第k个结点。找出解决方法
要求：尽可能高效
例如：一个链表有6个结点，（1,2,3,4,5,6）
这个链表的倒数第3个结点是：值为4的结点

2.1 算法设计思想

先遍历获得链表长度listlen(L)；

然后计算得出倒数第k个节点的正数位置，也就是listlen(L)-k+1；

遍历到listlen(L)-k+1的节点，然后输出

2.2 源代码

/* 求链表长度 */
int listlen(LinkList L){
  int len=0;
  Node *head=L;
  while(head->next!=NULL){
    len++;
    head=head->next;
  }
  return len;
}

// main
scanf("%d", &k);
for(i=0; i<listlen(L)-k+1; i++){
  p=p->next;
}

2.3 运行情况截图

---

---

题目3

在O(1)时间删除单链表结点；
给定单链表L及其中一个结点地址p,定义一个函数实现在O(1)时间删除该结点。

3.1 算法设计思想

将节点p的下一个节点的值赋给p；
p的后继指向p的后继的后继；
然后free掉p的后继

3.2 源代码

void InitLinkList(LinkList *L, LinkList *temp) {
  *L = (LinkList)malloc(sizeof(Node));
  (*L)->next = NULL;
  Node *r=*L, *s;
  int i=0;
  while(i<10){
    s=(Node*)malloc(sizeof(Node));
    s->data=i;
    r->next=s;
    s->next=NULL;
    if(i==5){   // 记住一个节点地址
      *temp=r;
    }
    r=s;
    i++;
  }
}

// main
InitLinkList(&L, &p);

s=p->next;
p->data = s->data;
p->next=s->next;
free(s);

3.3 运行情况截图

---

---

题目4

假定用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间，例如：loading和being。
  - 设计一个高效的算法，找出str1和str2的共同后缀的起始位置。（可能有也可能没有。）
  - 分析算法的时空效率

4.1 算法设计思想

分别获得链表str1和str2的长度；
移动长度较长的链表的头指针，使得两指针的起始位置相同；
然后同时往后移动，遇到相同地址的节点即为共同后缀的起始位置

4.2 源代码

LinkList reverse(LinkList L){
  if(L->next == NULL || L->next->next == NULL)  {
    return L;   /*链表为空或只有一个元素则直接返回*/
  }
  Node *r, *p = L->next, *q = L->next->next;
  while(q != NULL){        
    r = q->next;
    q->next = p;
    p = q;
    q = r;
  }

  /*此时q指向原始链表最后一个元素，也是逆转后的链表的表头元素*/
  L->next->next = NULL;  /*设置链表尾*/
  L->next = p;           /*调整链表头*/
  return L;
}

LinkList commonSuffix1(LinkList L1, LinkList L2){
  Node *p, *q;
  int len1, len2;
  len1=listlen(L1);
  len2=listlen(L2);
  if(lastNode(L1) != lastNode(L2)){
    return NULL;
  }
  else{
    for(p=L1; len1>len2; len1--){
      p=p->next;
    }
    for(q=L2; len2>len1; len2--){
      q=q->next;
    }
    while(p->next != NULL && p->next != q->next){
      p=p->next;
      q=q->next;
    }
    return p->next;
  }
}

LinkList commonSuffix2(LinkList L1, LinkList L2){
  Node *p=L1, *q=L2;
  if(L1->next == NULL || L2->next == NULL){   // 空，直接返回
    return NULL;
  }
  // else if(L1->next != L2->next){   // 这里的第一个元素,是原来的最后一个元素
  //   return NULL;    // 不相等直接返回
  // }
  else{
    while(p->next != NULL && q->next != NULL && p->next != q->next){
      p=p->next;
      q=q->next;
    }
    return p->next;
  }
}

4.3 运行情况截图

---