有没有单纯做旅游攻略的网站,网站建设招商,租点点电脑租赁公司,广州地铁集团有限公司反转单链表 题目描述 题目分析 先来说迭代的思想#xff1a; 上面next cur-next应该放在cur-next pre前面执行#xff0c;这里笔误
再来说递归的思想#xff1a; 题目代码 这个代码里面我加了我自己写的测试数据#xff0c;自己可以去找对应的部分#xff0c…反转单链表 题目描述 题目分析 先来说迭代的思想 上面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) 5cur假设当前指针是这样来指的//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;//这一步放在curnext,这里就是先赋值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;
}好了祝早安午安晚安
