链表反转算法

2020-01-02 08:40:43来源：博客园阅读 ()

链表反转算法

闲余时间把看了一些常见的算法题,把链表对应的常见算法写了一下如有疑问可加我QQ:1051980588共同探讨

  1 package com.trs.codetool.sort;
  2 
  3 /**
  4  * @author zheng.changgang
  5  * @date 2020-01-02 09:57
  6  * 链表的常见算法
  7  */
  8 public class LianBiao {
  9     static Node  head = new Node(0);
 10     public static void main(String[] args) {
 11         int[] nums = {1,2,3,4,5};
 12         for(int i=0;i<nums.length;i++) {
 13             addNode(nums[i]);
 14         }
 15         //printNode(head);
 16 
 17      /*  // 递归反转链表
 18         Node invertNode = invertLinkedList(head.next);
 19         System.out.println();
 20         head.next = invertNode;
 21         printNode(head);
 22         // 非递归反转链表
 23         iterationInvertLinkedList(head);
 24         printNode(head);
 25         Integer from = 2;
 26         Integer to = 4;
 27         // 变形题 1：给定一个链表的头结点 head,以及两个整数 from 和 to ,在链表上把第 from 个节点和第 to 个节点这一部分进行翻转。例如：给定如下链表，from = 2, to = 4 head-->5-->4-->3-->2-->1 将其翻转后，链表变成 head-->5--->2-->3-->4-->1
 28         iterationInvertLinkedList(head,from,to);
 29         printNode(head);**/
 30        // 变形题 2：给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序
 31         iterationInvertLinkedListEveryK(2);
 32         printNode(head);
 33 
 34     }
 35 
 36     /**
 37      * 每 k 个一组翻转链表
 38      * @param k
 39      */
 40     public static void iterationInvertLinkedListEveryK(int k) {
 41         Node tmp = head.next;
 42         int step = 0;               // 计数，用来找出首结点和尾结点
 43 
 44         Node startK = null;         // k个一组链表中的头结点
 45         Node startKPre = head;      // k个一组链表头结点的前置结点
 46         Node endK;                  // k个一组链表中的尾结点
 47         while (tmp != null) {
 48             // tmp 的下一个节点,因为由于翻转，tmp 的后继结点会变,要提前保存
 49             Node tmpNext = tmp.next;
 50             if (step == 0) {
 51                 // k 个一组链表区间的头结点
 52                 startK = tmp;
 53                 step++;
 54             } else if (step == k-1) {
 55                 // 此时找到了 k 个一组链表区间的尾结点（endK）,对这段链表用迭代进行翻转
 56                 endK = tmp;
 57                 Node pre = null;
 58                 Node cur = startK;
 59                 if (cur == null) {
 60                     break;
 61                 }
 62                 Node endKNext = endK.next;
 63                 while (cur != endKNext) {
 64                     Node next = cur.next;
 65                     cur.next = pre;
 66                     pre = cur;
 67                     cur = next;
 68                 }
 69                 // 翻转后此时 endK 和 startK 分别是是 k 个一组链表中的首尾结点
 70                 startKPre.next = endK;
 71                 startK.next = endKNext;
 72 
 73                 // 当前的 k 个一组翻转完了，开始下一个 k 个一组的翻转
 74                 startKPre = startK;
 75                 step = 0;
 76             } else {
 77                 step++;
 78             }
 79             tmp = tmpNext;
 80         }
 81     }
 82 
 83     /**
 84      * 变形题 1：给定一个链表的头结点 head,以及两个整数 from 和 to ,在链表上把第 from 个节点和第 to 个节点这一部分进行翻转。例如：给定如下链表，from = 2, to = 4 head-->5-->4-->3-->2-->1 将其翻转后，链表变成 head-->5--->2-->3-->4-->1
 85      * @param head
 86      * @param fromIndex
 87      * @param toIndex
 88      */
 89     private static void iterationInvertLinkedList(Node head, Integer fromIndex, Integer toIndex) {
 90         // from-1结点
 91         Node fromPre = null;
 92         Node from = null;
 93         Node to = null;
 94         Node toNext = null;
 95         Integer index = 1;
 96         Node temp = head.getNext();
 97         // 记录之前的节点
 98         while (temp != null) {
 99             if(fromIndex-1 == index) {
100                 fromPre = temp;
101             } else if(fromIndex == index) {
102                 from = temp;
103             } else if(toIndex+1 == index) {
104                 toNext = temp;
105             } else if(toIndex == index) {
106                 to = temp;
107             }
108             index++;
109             temp = temp.next;
110         }
111 
112         Node pre = null;
113         Node cur =from;
114         while (cur != toNext) {
115             Node next = cur.getNext();
116             cur.setNext(pre);
117             pre = cur;
118             cur = next;
119         }
120         // 步骤3：将 from-1 节点指向 to 结点（如果从 head 的后继结点开始翻转，则需要重新设置 head 的后继结点），将 from 结点指向 to + 1 结点
121         if (fromPre != null) {
122             fromPre.next = to;
123         } else {
124             head.next = to;
125         }
126         from.next = toNext;
127 
128     }
129 
130     /**
131      * 递归反转链表
132      * @param node
133      * @return
134      */
135     private static Node invertLinkedList(Node node) {
136         if(node.next == null) {
137             return node;
138         }
139         Node newHead = invertLinkedList(node.next);
140         node.next.next = node;
141         node.next = null;
142         return newHead;
143     }
144 
145     /**
146      * 非递归反转
147      * @param node
148      */
149     private static void iterationInvertLinkedList(Node node) {
150         Node pre = null;
151         Node cur = node.next;
152         while (cur != null) {
153             Node next = cur.next;
154             cur.setNext(pre);
155             pre = cur;
156             cur = next;
157         }
158         node.setNext(pre);
159 
160     }
161 
162     /**
163      * 打印节点
164      */
165     private static void printNode(Node temp) {
166         Node cur = temp.next;
167         while (cur != null) {
168             if(cur.next != null) {
169                 System.out.print(cur.getValue()+"->");
170             } else {
171                 System.out.print(cur.getValue());
172             }
173             cur = cur.next;
174         }
175     }
176 
177     /**
178      * 添加节点
179      * @param num
180      */
181     private static void addNode(int num) {
182         Node cur = head;
183          while (cur.next != null) {
184              cur = cur.next;
185          }
186          cur.next = new Node(num);
187     }
188 
189     static class Node {
190         private Integer value;
191         private Node next;
192 
193         public Node(Integer value) {
194             this.value = value;
195         }
196 
197         public Integer getValue() {
198             return value;
199         }
200 
201         public void setValue(Integer value) {
202             this.value = value;
203         }
204 
205         public Node getNext() {
206             return next;
207         }
208 
209         public void setNext(Node next) {
210             this.next = next;
211         }
212     }
213 }