剧情反转,单链表反转代码

链表的一般数据结构

链表是物理存储单元上的非连续、非顺序存储结构，数据元素的逻辑顺序通过链表中指针链接的顺序来实现。 链表由一组节点组成，链表中的每个元素都称为节点，节点可以在运行时动态生成。 每个节点有两个部分：存储数据元素的数据域和存储以下节点地址的指针域。 与线性表的顺序结构相比，操作更为复杂。 由于不需要按顺序保存，所以链表在插入时可以达到o(1)的复杂度，比另一个线性表的顺序表快得多，但查找一个节点或访问特定编号的节点需要o ) n )的时间。 与线性表和顺序表相对应的时间复杂度分别为o ) logn )和o )1)。

谈谈链表的反转

链表的翻转目前主要包括三种

1 .链表整体翻转

2 .从链表的第一个节点开始的前n个节点

3 .反转链表从指定m到n的节点M=1

首先开始第一个操作

1 .整个链表的反正

1.1方法不递归代码虽然不优雅，但很难快速发生堆栈溢出

直接加码

/** *单链表节点的结构*/staticclasslistnode { listnode next； int val； listnode(intx ) { this.val=x； 定义//1到6的链表专用静态最终列表头； 静态{ head=new listnode (1； listnodetwo=newlistnode(2； listnodethree=newlistnode(3； listnodefour=newlistnode(4； listnodefive=newlistnode(5； listnodesix=newlistnode(6； HEAD.next=two； two.next=three； three.next=four； four.next=five； five.next=six； six.next=空值； } publiclistnoderevertlist (listnode head )//当前节点从头节点开始列出ListNode cur=head； ListNode pre=null； ListNode tmp； wile(cur！=null(//记录当前节点的下一个节点tmp=head.next的cur.next=pre； pre=cur； cur=tmp； }返回前； }简要介绍循环的想法。 //此处简单易懂地表示链表节点的数字。 //1-2-3--4--5-6//1第一次循环cur=head=1tmp=2cur.next=1--2--1--null pre=1第二次循环tmp=3 cur.next=3tmp=4cur.next=前3---4---3--2pre=3cur=4///44 tmp=5cur.next=前4---5---3 pre=4cur

publicstaticlistnoderevert (listnode head ) if ) head.next==null ) { return head； //6 listnode last=revert (head.next )； system.out.println(last: ) last.val )； system.out.println (' head : ' head.val )； system.out.println (head next : ) head.next.val )； head.next.next=head； System.out.println (赋值head: ) head.val )； head.next=null； 返回最后； //原始链表1-2-3-4-5-6//调用第一个方法时的1 revert参数-1//第二个2。

revert 参数 -> 2//第三次 3 revert 参数 -> 3//第四次 4. revert 参数 -> 4//第五次 5.revert 参数 -> 5//第六次 6.revert 参数 ->6 return last 6 方法结束//回到第五次 head = 5 head.next.next= 6.next = 5 5->6 6->5 成环//下一步操作 head.next = null 5.next = null 即此时链表恢复正常 6->5 返回 last = 6//第四次 head = 4 head.next.next= 5.next =4 4->5 5->4 成环//下一步操作 head.next = null 4.next =null 返回 上一步操作 链表为 6->5 经过此次操作 5->4 最后此时链表为 6->5->4 返回 last=6//第三次 head = 3 head.next.next= 3.next =3 3->4 4->3 成环//下一步操作 head.next = null 3.next =null 返回 最后此时链表为 6->5->4->3 返回 last=6//第二次 head = 2 head.next.next= 2.next=2 2->3 3->2 成环//下一步操作 head.next = null 2.next =null 返回 最后此时链表为 6->5->4->3->2 返回 last=6//第一次操作 head =1 head.next.next= 2.next=1 1->2 2->1 成环//下一步操作 head.next = null 1.next = null 返回 最后此时链表为 6->5->4->3->2->1 返回 last=6//至此操作翻转完成

配置打印的注释帮助理解一波

以上常见两种反转链表操作

2.反转链表的前N个节点 

private static ListNode successor;/** * 反转链表前 N 个节点 * * @param head head * @param n n * @return ListNode */private static ListNode revertN(ListNode head, Integer n) { if (n == 1) { // 记录第 n + 1 个节点 successor = head.next; return head; } ListNode last = revertN(head.next, n - 1); head.next.next = head; head.next = successor; return last;}// revertN(HEAD,3) head = 1 n =3// 第二次 head.next =2 n-1=3-1=2// 第三次 head.next =3 n-1 = 2-1 = 1 返回 head =3// 返回第二次 head =2 2.next.next = head -----> 2->3->4->5->6 ---> 2->3->2 head.next = 3->2->4->5->6//第二步重点 2->3->2 2.next = 2->4 但是 3还是->2的 也就变成 3->2->4->5->6// 返回第一次 head =1 1.next.next= 1->2->3 ---> 1--->2-->1 head.next= = 1-> 4 = 3->2->1->4->5->6//第一步重点 1->2->1 1.next =1->4 但是 2还是->1的 也就变成 3->2->1->4->5->6

3.反转链表的m - n个节点  其中m>=1  

private static ListNode revertBetween(ListNode head, Integer m, Integer n) { if (m == 1) { return revertN(head, n); } // 前进到反转的起点触发 base case head.next = revertBetween(head.next, m - 1, n - 1); return head;}//第一次 revertBetween(HEAD,3,5) 实际传入值 head=1 m=3 n=5//第二次调用 head=1 head.next=2 m-1=2 n-1=4 实际传入值 head=2 m=2 n=4///第三次调用 head=2 head.next=3 m-1=1 n-1=3 回到 revertN(3,3)//进入 revertN(3,3) 3->4->5->6 反转前3个 返回 5->4->3->6//回到第二次 head =2 head.next = 2->5->4->3->6//回到第一次 head = 1 head.next = 1->2->5->4->3->6

学习文章  https://mp.weixin.qq.com/s/5wz_YJ3lTkDH3nWfVDi5SA

--------------------------------------------------------20210802-----------------------------------------------------------

循环反转 a->b之间的节点

/** * 反转a->b节点 * * @param a a * @param b b * @return ListNode */private static ListNode reverse(ListNode a, ListNode b) { ListNode cur = a; //pre = a ListNode pre = null; ListNode next; while (cur != b) { next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre;}

进阶 K 个一组反转链表

/** * k个节点一组翻转链表 * * @param head head * @param k k * @return ListNode */private static ListNode reverseGroup(ListNode head, int k) { ListNode b = head; for (int i = 0; i < k; i++) { if (b == null) { return head; } b = b.next; } ListNode newHead = reverse(head, b); head.next = reverseGroup(b, k); return newHead;}