反转单链表

题目描述

题目分析 

先来说迭代的思想：

上面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) {
        //空结点，直接返回一个null
        if (head == null) {
            return null;
        }
        //定义三个指针进行迭代
        ListNode pre = head, cur = head.next, next;//next用于在中间轮替指针可以先不用初值
        //没循环之前先把第一个结点next指向null
        head.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与cur
            pre = cur;//这一步放在cur=next,这里就是先赋值pre,在改变cur
            cur = 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;
}

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