C語言的單連結清單逆序和指定範圍逆序

文章目錄

• ​​前言​​
• ​​逆序​​
• ​​指定範圍逆序​​
• ​​源碼實作​​

前言

關于連結清單的逆置，是考察對連結清單指針的了解。知道了如何不實用額外空間，同時使用O(n)複雜度對連結清單進行逆序之後将會對連結清單有好了解。

同時關于如何在指定範圍内對連結清單逆置同樣可以進一步加深了解

逆序

基本過程如下：

1. 保留原始連結清單的next指針域,p = head -> next
2. 将原始連結清單的next指針域指向新連結清單的頭部,head -> next = new_head
3. 新連結清單指針向前移動一位,new_head = head
4. 原始連結清單頭指針向後移動一位，指向之前保留的原始指針的next域，head = p

···

以上過程實作如下:

Data *reverse(Data *head) {
  Data *new_head = NULL;
  while(head) {
    Data *p = head -> next;
    head -> next = new_head;
    new_head = head;
    head = p;
  }
  return new_head;
}      

指定範圍逆序

基本過程如下，指定連結清單的第2-4個節點進行逆序，其他節點保持原有順序

這個過程需要關注如下幾個關鍵節點

1. 逆序前的頭節點和逆序後的尾節點需要确認，确認之後在此範圍即可進行如上過程的連結清單逆序
2. 逆序完成之後需要連接配接頭節點
3. 逆序完成之後需要連接配接尾節點

/*指定範圍，逆序m-n之間的節點*/
Data *reverse_betweenM_N(Data *head, int m, int n) {
  Data *result, new_tail;
  Data *new_head = NULL;
  Data *pre_head = NULL;
  
  /*計算需要逆序的節點個數，進而能夠找到逆序的尾節點*/
  int change = n - m + 1;
  
  /*跳過m個節點，找到逆序前的第一個節點*/
  result = head;
  while(head && --m) {
    pre_head = head;
    head = head -> next;
  }
  
  /*保留逆序前的第一個節點，逆序後将變為尾節點*/
  Data *list_tail = head;

  /*逆序m-n之間的節點*/
  while(head && change) {
    Data *p = head -> next;
    head -> next = new_head;
    new_head = head;
    head = p;
    change --;
  }
  
  /*逆序完成之後，将逆序後的尾節點指向連結清單結尾*/
  list_tail -> next = head;

  /*
  确認逆序節點不是從連結清單頭節點開始：
  如果是則最終頭節點為逆序後的頭節點
  否則将頭節點指向逆序後的頭節點，保持連結清單完成性
  */
  if (pre_head) {
    pre_head -> next = new_head;
    result = pre_head;
  } else {
    result = new_head;
  }
  return result;
}      

源碼實作

#include <stdio.h>
#include <stdlib.h>

/*連結清單資料域和指針域*/
typedef struct link_list {
    int data;
    struct link_list *next;
}Data;

/*列印連結清單*/
void print_list(Data *head) {
    while (head) {
        printf("%d ",head->data);
        head = head -> next;
    }
    printf("\n");
}

/*頭插法建立連結清單*/
Data *insert_head(Data *head, int n) {
    head = (Data *)malloc (sizeof(Data));
    head -> next = NULL;
    int data;
    while(n --) {
        Data *p = (Data *)malloc(sizeof(Data));
        scanf("%d",&data);

        p -> data = data;
        p -> next = head -> next;
        head -> next = p;
    }
    return head;
}

/*尾插法建立連結清單*/
Data *insert_tail(Data *head, int n) {
    head = (Data *)malloc(sizeof(Data));
    head -> next = NULL;
    Data *r = head;
    int data;
    while(n--) {
        Data *p = (Data *)malloc(sizeof(Data));
        scanf("%d", &data);

        p -> data = data;
        r -> next = p;
        r = p;
        p -> next = NULL;
    }
    return head;
}

/*連結清單逆序*/
Data *reverse(Data *head) {
    Data *new_head = NULL;
    while(head) {
        Data *p = head -> next;
        head -> next = new_head;
        new_head = head;
        head = p;
    }
    return new_head;
}

/*連結清單指定範圍逆序*/
Data *reverse_betweenM_N(Data *head, int m, int n) {
    Data *result, new_tail;
    Data *new_head = NULL;
    Data *pre_head = NULL;
    int change = n - m + 1;

    result = head;
    while(head && --m) {
        pre_head = head;
        head = head -> next;
    }

    Data *list_tail = head;
    while(head && change) {
        Data *p = head -> next;
        head -> next = new_head;
        new_head = head;
        head = p;
        change --;
    }
    list_tail -> next = head;

    if (pre_head) {
        pre_head -> next = new_head;
        result = pre_head;
    } else {
        result = new_head;
    }
    return result;
}

int main() {
    Data *head;
    printf("construct link list :\n");
    head = insert_tail(head,5);
    Data *test = reverse_betweenM_N(head -> next,2,4);
    printf("after reverse between 2-4:\n");
    print_list(test);
    Data *rever = reverse(head -> next);
    printf("after reverse :\n");
    print_list(rever);

    return 0;
}      

construct link list :
1 2 3 4 5
after reverse between 2-4:
1 4 3 2 5 
after reverse :
5 2 3 4 1