将单链表的每k个节点之间逆序

xiaoxiao2021-02-28  10

import java.util.Stack; //将单链表的每k个节点之间逆序 public class ReverseKOfList{ //单链表节点的定义 public static class Node{ public int value; public Node next; public Node(int data) { this.value=data; } } //(方法一、反转部分链表法)每k个节点之间逆序 public static Node ReverseK(Node head,int k) { if(head==null||k<=0) { return head; } if(k==1) { return head; } int n=0; //记录链经历的节点数 Node p=head; //记录链表的头节点 Node q=head; int leng=0; while(q!=null) { ++leng; q=q.next; } //n=(int)Math.floor(leng/k); n=leng/k; //记录反转的次数 //System.out.println(n); int from=1; int to=k; while(n>0) { Node mode=reverseSublist(head,from,to); //记录每次变换后的链表头节点 //PrintList(mode); head=mode; from+=k; to+=k; n--; } return head; } //反转部分链表 public static Node reverseSublist(Node head, int from,int to) { if(head==null||from <0||to<0) { return head; } Node p=head; int leng=0; Node tPre=null; //获取反转起始节点的前一个节点 Node tPos=null; //获取反转结束节点的后一个节点 //计算链表长度 while(p!=null) { ++leng; tPre=(leng==from-1?p:tPre); //找到反转起始节点的前一个节点 tPos=(leng==to+1?p:tPos); //找到反转结束节点的后一个节点 p=p.next; } if(from>leng||to>leng||from>to) { return head; } p=tPre==null?head:tPre.next; //找到要起始反转的节点 Node node2=p.next; p.next=tPos; //起始反转的节点指向反转结束节点的后一个节点 Node next=null; while(node2!=tPos) { next=node2.next; node2.next=p; p=node2; node2=next; } if(tPre!=null) { tPre.next=p; return head; } return p; } //(方法二、利用栈结构)每k个节点之间逆序 public static Node ReverseK2(Node head, int K) { if (K < 2) { return head; } Stack<Node> stack = new Stack<Node>(); Node newHead = head; //记录新的头结点 Node cur = head; Node pre = null; Node next = null; while (cur != null) { next = cur.next; stack.push(cur); if (stack.size() == K) { pre = resign1(stack, pre, next); newHead = newHead == head ? cur : newHead; } cur = next; } return newHead; } //调整k个节点逆序 public static Node resign1(Stack<Node> stack, Node left, Node right) { Node cur = stack.pop(); if (left != null) { left.next = cur; } Node next = null; while (!stack.isEmpty()) { next = stack.pop(); cur.next = next; cur = next; } cur.next = right; return cur; } //(方法三、利用变量存储)每k个节点之间逆序 public static Node ReverseK3(Node head, int K) { if (K < 2) { return head; } Node cur = head; Node start = null; Node pre = null; Node next = null; int count = 1; while (cur != null) { next = cur.next; if (count == K) { start = pre == null ? head : pre.next; head = pre == null ? cur : head; resign2(pre, start, cur, next); pre = start; count = 0; } count++; cur = next; } return head; } //调整k个节点逆序 public static void resign2(Node left, Node start, Node end, Node right) { Node pre = start; Node cur = start.next; Node next = null; //链表的逆转 while (cur != right) { next = cur.next; cur.next = pre; pre = cur; cur = next; } if (left != null) { left.next = end; } start.next = right; } //打印链表 public static void PrintList(Node head) { while(head!=null) { System.out.print(head.value+" "); head=head.next; } System.out.println(); } public static void main(String[]args) { Node node=new Node(1); node.next=new Node(2); node.next.next=new Node(3); node.next.next.next=new Node(4); node.next.next.next.next=new Node(5); node.next.next.next.next.next=new Node(6); node.next.next.next.next.next.next=new Node(7); node.next.next.next.next.next.next.next=new Node(8); PrintList(node); //Node mode=ReverseK(node,3); //时间、空间复杂度大 //Node mode=ReverseK2(node,3);//时间O(n),空间O(k) Node mode=ReverseK3(node,3); //时间O(n),空间O(1) PrintList(mode); } }

转载请注明原文地址: https://www.6miu.com/read-1150004.html

最新回复(0)