反转单链表

题目描述

题目分析 

先来说迭代的思想：

上面next = cur->next应该放在cur->next = pre前面执行，这里笔误 

再来说递归的思想：

 题目代码

这个代码里面我加了我自己写的测试数据，自己可以去找对应的部分，直接粘贴赋值就可以在leetcode提交成功，我们就没有把迭代与递归单独分开了，里面还有大量的注释说明，请结合题目分析仔细观看

java版本

package com.pxx.test;import sun.awt.image.ImageWatched;class LinkList {private ListNode head;private int length;//长度//链表结点的一个定义static class ListNode {int value;ListNode next;//初始化一个结点public ListNode(int value) {this.value = value;this.next = null;}}public ListNode getHead() {return this.head;}//实现数据的尾插public void insertEnd(int value) {ListNode newNode = new ListNode(value);if (newNode != null) {if (head == null) {head = newNode;//指向第一个结点} else {ListNode cur = head;//移动到最后一个结点的位置while (cur.next != null) {cur = cur.next;}//最后一定是在cur加入结点cur.next = newNode;}length++;}}//打印public void printList(ListNode head) {ListNode cur = head;while (cur != null) {System.out.print(cur.value + " ");cur = cur.next;}System.out.println();}//利用递归反转链表//返回反转之后的链表头public ListNode reverse(ListNode head) {//安全检查都必须先进行操作if (head == null || head.next == null) {return head;} else {ListNode pre = head , cur = head.next;//接收最后一次的返回，就是最后一个节点，中间是没有结点要返回的//这里为什么传入pre.next，而不是cur.next//目的其实就是为了每一个值都能被链上，为什么那么说呢//1(pre) 2(cur) 3 4 5//如果按照cur.next来进行移动//1 <- 2这一部分递归了之后，就会进入 3(pre(cur会直接到3变成pre))   4（内部的cur）//那么我请问2 3中间这条线被狗吃了吗？所以以pre.next往下递归//上面pre循环到5号结点，也就是最后一组递归就要结束，因此有head.next = null就结束递归ListNode res = reverse(pre.next);cur.next = pre;//目的把第一个结点的next指向null//这里千万不能吧pre.next 与 cur.next进行比较//否则会造成最开头的两个数据一直轮替//这样来说 1  2  3  4(pre)  5（cur）假设当前指针是这样来指的//4 <- 5 此时4也还是4->5的，进入pre.next把指向变为了null（注意这是递归所以从后往前分析）//不太懂的请结合我的递归分析图来看//null <- 4 <- 5//那么就行往前递归3(pre) 4(cur) 5,也就是null <- 3 <- 4 <- 5//我们注意到一个问题就是4的pre已经在中间的时候被改向了第一个结点//那么对于1(pre) <- 2(cur)来说,1的.next又等于cur,所以1.pre = null//null <- 1 <- 2......这个时候，程序已经全部执行完if (pre.next == cur) {pre.next = null;}return res;}}//利用迭代思想实现public ListNode reverse1(ListNode head) {//空结点，直接返回一个nullif (head == null) {return null;}//定义三个指针进行迭代ListNode pre = head, cur = head.next, next;//next用于在中间轮替指针可以先不用初值//没循环之前先把第一个结点next指向nullhead.next = null;while (cur != null) {//这里迭代就是// null <- 1(pre) 2(cur) 3(next) 4        5// null <- 1 <-   2(pre) 3(cur)  4(next)  5// null <- 1 <-   2 <-   3(pre)  4(cur)   5(next)// null <- 1 <-   2 <-   3 <-    4(pre)   5(cur)   next(这个时候还会进入循环里面更改cur.next指针)//这个时候cur == null,结束,pre指向最后一个结点返回//保留next指向next = cur.next;//这一步必须放在cur.next前面，不然cur.next就被先改变了,next的位置就不对了cur.next = pre;//改变pre与curpre = cur;//这一步放在cur=next,这里就是先赋值pre,在改变curcur = next;}//最后一定是pre指向了最后一个结点return pre;}}public class Test4 {public static void main(String[] args) {LinkList linkList = new LinkList();//开始插入数据linkList.insertEnd(1);linkList.insertEnd(2);linkList.insertEnd(3);
//        linkList.insertEnd(4);
//        linkList.insertEnd(5);linkList.printList(linkList.getHead());//反转链表LinkList.ListNode head = linkList.reverse(linkList.getHead());linkList.printList(head);}
}

 c语言版本测试代码，仅做参考

#include <stdio.h>
#include <stdlib.h>// 链表结点的定义
struct ListNode {int value;struct ListNode* next;
};// 链表的定义
struct LinkedList {struct ListNode* head;int length;
};// 初始化链表
void initLinkedList(struct LinkedList* list) {list->head = NULL;list->length = 0;
}// 在链表末尾插入一个新节点
void insertEnd(struct LinkedList* list, int value) {struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));if (newNode != NULL) {newNode->value = value;newNode->next = NULL;if (list->head == NULL) {list->head = newNode;} else {struct ListNode* cur = list->head;while (cur->next != NULL) {cur = cur->next;}cur->next = newNode;}list->length++;}
}// 打印链表的元素
void printList(struct ListNode* head) {struct ListNode* cur = head;while (cur != NULL) {printf("%d ", cur->value);cur = cur->next;}printf("\n");
}// 递归反转链表
struct ListNode* reverse(struct ListNode* head) {if (head == NULL || head->next == NULL) {return head;} else {struct ListNode* pre = head;struct ListNode* cur = head->next;struct ListNode* res = reverse(pre->next);cur->next = pre;if (pre->next == cur) {pre->next = NULL;}return res;}
}int main() {struct LinkedList linkList;initLinkedList(&linkList);// 开始插入数据insertEnd(&linkList, 1);insertEnd(&linkList, 2);insertEnd(&linkList, 3);printList(linkList.head);// 反转链表linkList.head = reverse(linkList.head);printList(linkList.head);return 0;
}

好了，祝早安，午安，晚安