首页 / JAVA / Java——每k个结点反转一次链表
Java——每k个结点反转一次链表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java——每k个结点反转一次链表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1955字,纯文字阅读大概需要3分钟。
内容图文
前几日,看到一道面试题,每k个结点反转一次链表,要求输出反转后的链表。
题目意思如下:
原链表:1,2,3,4,5,6,7,8
k = 3
新链表:3,2,1,6,5,4,8,7
觉得还是有点意思,今天便做了,思路是把原链表先按k切割成多份,再把每一份都反转并拼接起来。
把代码贴出来供大家参考
public class Node { public int v; public Node next; public Node(int v, Node next) { this.v = v; this.next = next; } public Node(int v) { this.v = v; } public Node() { } publicstatic Node getNode(int ... arr) { Node head = new Node(); Node root = head; for (int i : arr) { head.next = new Node(i); head = head.next; } return root.next; } /** * 反转链表 */publicstatic Node reverse(Node head) { if (head == null) { returnnull; } Node pre = null; Node cur = head; Node aft = head.next; while (aft != null) { cur.next = pre; pre = cur; cur = aft; aft = aft.next; } cur.next = pre; return cur; } /** * 每k位反转 */publicstatic Node reverseK(Node head, int k) { List<CutRes> cutResList = new ArrayList<>(); while (head != null) { CutRes cutRes = cut(head, k); cutResList.add(cutRes); head = cutRes.newHead; } Node cur = new Node(); Node pre = cur; for (CutRes cutRes : cutResList) { cur.next = Node.reverse(cutRes.head); cur = cutRes.head; } return pre.next; } /** * 从头部切割链表 * @param head 原头部 * @param k 切割长度 */publicstatic CutRes cut(Node head, int k) { if (k <= 0) { returnnew CutRes(null, head); } Node cur = head; int i = 0; while (cur.next != null && ++i < k) { cur = cur.next; } Node tail = cur; Node newHead = cur.next; tail.next = null; returnnew CutRes(head, newHead); } staticclass CutRes { Node head; //切割得到的头部 Node newHead; //切割后剩余的头部public CutRes(Node head, Node newHead) { this.head = head; this.newHead = newHead; } @Override public String toString() { return head.toString(); } } @Override public String toString() { StringBuilder sb = new StringBuilder("["); Node cur = next; sb.append(v); while (cur != null) { sb.append(", "); sb.append(cur.v); cur = cur.next; } sb.append(‘]‘); return sb.toString(); } }
原文:https://www.cnblogs.com/elucidator/p/11296547.html
内容总结
以上是互联网集市为您收集整理的Java——每k个结点反转一次链表全部内容,希望文章能够帮你解决Java——每k个结点反转一次链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。