【数据结构与算法】对单链表实现就地逆置_单链表就地逆置

前言

在学习数据结构与算法的链表知识点时，布置了一个有关链表转置操作的小作业，感觉主要难点就是需要实现就地逆置，很容易就会使用额外的空间来帮助这个单链表逆置。废话不多说，我们下面一起来看看题目是怎么样的。

---

题目以及要求

写一算法，对单链表实现就地逆置。

---

思想以及代码

这道题的主要难点就是要在不开辟新的空间的情况下和以及在保证链表不断的情况下，实现链表的逆置。

我解这道题的思路是：

1. 计算链表L的长度（元素个数）

2. 开始循环

3. 使指针P指向最后一个节点（node -> next = null）

4. 保证不断的情况下实现元素调换

5. 进入下次循环

6. 循环n - 1次后退出（n为链表L的长度）

---

code photo

---

diagrammatize

---

code

//找到链表L的最后一个元素
int * ListEnd(LinkList L){
    LinkList *p;
    p = first;
    while(p){
        p = p -> next;
    }
    return p;
}
//单链表的长度（元素个数）
int ListLength(LinkList L){
    LinkList p;
    p = first;
    int count = 0;
    while(p){
        p = p -> next; count ++;
    }
    return count;
}
//实现对单链表就地逆置
void ListReverse{
    int n;
    //算出L的长度
    n = LinkLength(L);
    //使得p指向最后一个节点
    p = ListEnd(L);
    //q指向是p的前驱节点
    // q -> next = p;
    q = GetPrior(L,p);//该部分代码未给出
    //进行n - 1 次循环
    for(int i = 0; i < n - 1; i++){
        p -> next = L -> next;
        L -> next = q -> next;
        //将q的指针域置空
        q -> next = null;
        //p指向q所指的指针
        p = q;
        //q所指的节点再次变成p的前驱节点
        q -> next = p;
    }
}

---

结束语

因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！