其它解法

chenweijie · chenweijie · commit 47247631d12d · 2020-10-24T23:22:17.000+08:00
diff --git a/src/main/java/com/chen/algorithm/study/test25/ListNode.java b/src/main/java/com/chen/algorithm/study/test25/ListNode.java
@@ -0,0 +1,26 @@
+package com.chen.algorithm.study.test25;
+
+/**
+ * @author :  chen weijie
+ * @Date: 2019-09-02 23:06
+ * 参考 Solution3
+ */
+public class ListNode {
+
+    int val;
+
+    ListNode next;
+
+    ListNode() {
+    }
+
+    ListNode(int val) {
+        this.val = val;
+    }
+
+    ListNode(int val, ListNode next) {
+        this.val = val;
+        this.next = next;
+    }
+
+}
diff --git a/src/main/java/com/chen/algorithm/study/test25/Solution5.java b/src/main/java/com/chen/algorithm/study/test25/Solution5.java
@@ -0,0 +1,92 @@
+package com.chen.algorithm.study.test25;
+
+/**
+ * @Auther: zhunn
+ * @Date: 2020/10/24 17:23
+ * @Description: K个一组翻转链表
+ */
+public class Solution5 {
+
+    /**
+     * 官网解法
+     * @param head
+     * @param k
+     * @return
+     */
+    public ListNode reverseKGroup(ListNode head, int k) {
+        ListNode hair = new ListNode(0);
+        hair.next = head;
+        ListNode pre = hair;
+
+        while (head != null) {
+            ListNode tail = pre;
+            // 查看剩余部分长度是否大于等于 k
+            for (int i = 0; i < k; ++i) {
+                tail = tail.next;
+                if (tail == null) {
+                    return hair.next;
+                }
+            }
+            ListNode nextTemp = tail.next;
+            ListNode[] reverse = myReverse(head, tail);
+            head = reverse[0];
+            tail = reverse[1];
+            // 把子链表重新接回原链表
+            pre.next = head;
+            tail.next = nextTemp;
+            pre = tail;
+            head = tail.next;
+        }
+
+        return hair.next;
+    }
+
+    private ListNode[] myReverse(ListNode head, ListNode tail) {
+        ListNode prev = tail.next;
+        ListNode p = head;
+        while (prev != tail) {
+            ListNode nex = p.next;
+            p.next = prev;
+            prev = p;
+            p = nex;
+        }
+        return new ListNode[]{tail, head};
+    }
+
+
+    public ListNode reverseKGroup1(ListNode head, int k) {
+        ListNode dummy = new ListNode(0);
+        dummy.next = head;
+
+        ListNode pre = dummy;
+        ListNode end = dummy;
+
+        while (end.next != null) {
+            for (int i = 0; i < k && end != null; i++){end = end.next;}
+            if (end == null) {break;}
+            ListNode start = pre.next;
+            ListNode next = end.next;
+            end.next = null;
+            pre.next = reverse(start);
+            start.next = next;
+            pre = start;
+
+            end = pre;
+        }
+        return dummy.next;
+    }
+
+    private ListNode reverse(ListNode head) {
+        ListNode pre = null;
+        ListNode curr = head;
+        while (curr != null) {
+            ListNode next = curr.next;
+            curr.next = pre;
+            pre = curr;
+            curr = next;
+        }
+        return pre;
+    }
+
+
+}
diff --git a/src/main/java/com/chen/algorithm/study/test92/Solution3.java b/src/main/java/com/chen/algorithm/study/test92/Solution3.java
@@ -0,0 +1,120 @@
+package com.chen.algorithm.study.test92;
+
+import org.junit.Test;
+
+/**
+ * @Auther: zhunn
+ * @Date: 2020/10/24 17:23
+ * @Description: 反转链表二：1-双指针，2-删除结点递推
+ */
+public class Solution3 {
+
+    class ListNode {
+        int val;
+        ListNode next;
+
+        ListNode(int x) {
+            val = x;
+        }
+    }
+
+    // 翻转n个节点，返回新链表的头部
+    private ListNode reverseN(ListNode head, int n) {
+        ListNode prev = null;
+        ListNode curr = head;
+        for (int i = 0; i < n; i++) {
+            ListNode oldNext = curr.next;
+            curr.next = prev;
+            prev = curr;
+            curr = oldNext;
+        }
+        return prev;
+    }
+
+    /**
+     * 1-双指针
+     * @param head
+     * @param m
+     * @param n
+     * @return
+     */
+    public ListNode reverseBetween1(ListNode head, int m, int n) {
+        ListNode dummy = new ListNode(42);
+        dummy.next = head;
+        ListNode ptr1 = dummy;
+        ListNode ptr2 = dummy;
+        // 找到左右两段的端点
+        for (int i = 0; i < m - 1; i++) {
+            ptr2 = ptr2.next;
+        }
+        for (int i = 0; i < n + 1; i++) {
+            ptr1 = ptr1.next;
+        }
+        // 找到中段的尾端点
+        ListNode t = ptr2.next;
+        // 翻转中段，得到中段的头端点
+        ListNode h = reverseN(t, n - m + 1);
+        // 中端的头端点和左段端点相连
+        ptr2.next = h;
+        // 中段的尾端点和右段端点相连
+        t.next = ptr1;
+        return dummy.next;
+    }
+
+    /**
+     * 2-删除结点递推
+     * @param head
+     * @param m
+     * @param n
+     * @return
+     */
+    public ListNode reverseBetween2(ListNode head, int m, int n){
+        if(head == null || head.next == null){
+            return head;
+        }
+
+        ListNode dummy = new ListNode(-1);
+        dummy.next = head;
+        ListNode pre = dummy;
+        for(int i =0;i<m-1;i++){
+            pre = pre.next;
+            head = head.next;
+        }
+
+        for (int i = m; i <n ; i++) {
+            ListNode nextTemp = head.next;
+            head.next =nextTemp.next;
+            nextTemp.next = pre.next;
+            pre.next = nextTemp;
+        }
+        return dummy.next;
+    }
+
+    @Test
+    public void test() {
+        ListNode l1_1 = new ListNode(7);
+        ListNode l1_2 = new ListNode(9);
+        ListNode l1_3 = new ListNode(2);
+        ListNode l1_4 = new ListNode(10);
+        ListNode l1_5 = new ListNode(1);
+        ListNode l1_6 = new ListNode(8);
+        ListNode l1_7 = new ListNode(6);
+
+        l1_1.next = l1_2;
+        l1_2.next = l1_3;
+        l1_3.next = l1_4;
+        l1_4.next = l1_5;
+        l1_5.next = l1_6;
+        l1_6.next = l1_7;
+
+        ListNode result = reverseBetween1(l1_1,3,6);
+
+        System.out.println(result.val);
+        System.out.println(result.next.val);
+        System.out.println(result.next.next.val);
+        System.out.println(result.next.next.next.val);
+        System.out.println(result.next.next.next.next.val);
+        System.out.println(result.next.next.next.next.next.val);
+        System.out.println(result.next.next.next.next.next.next.val);
+    }
+}
