K个一组翻转链表

LeetCode原题链接

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例1

示例1

1
2
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例2

示例2

1
2
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

**进阶：**你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

题目分析

这题难度被划归为困难，其实显然是不能达到困难题的难度的，只不过如果不习惯封装编程，单独将反转链表的方法单独写的话可能会有一些边界类型的问题出现。不过提到了需要使用 O(1) 额外内存空间，前置题目为反转链表，题目链接为：反转链表，只不过反转链表提到可以使用递归或者迭代的方式，但是递归的方式显然需要使用系统栈，无法实现额外内存空间需求，所以这题几乎已经锁定使用迭代的方式进行反转。

首先我们先尝试做一下反转链表这道题目

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

官方定义的链表结构还是比较简单的，没有要用户自己定义链表，有些企业的面试题是需要自己定义的嘛，所以我们也简单自己定义一下，防患未然了属于是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
*定义链表
*/
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;
	}
}

在实现任务之前，先简单实现一个输入获取和结果打印的方法，便于本地自行测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static ListNode readDate(){
    Scanner sc = new Scanner(System.in);
    String[] vals = sc.nextLine().replaceAll("^\\[*|\\]*$", "").split(",");
    ListNode head = new ListNode();
    ListNode pre = head;
    for(String val:vals){
        pre.next = new ListNode(Integer.valueOf(val));
        pre = pre.next;
    }
    return head.next;
}

public static void printListNode(ListNode head){
    StringBuffer sb = new StringBuffer();
    while(null != head){
        sb.append(head.val).append(",");
        head = head.next;
    }
    sb.deleteCharAt(sb.length()-1);
    System.out.println(sb.toString());
}

接下来就是正常实现了，我们分为两种方式实现吧，首先是比较简单的递归的方式实现，递归的方式就是不断把后半段反转然后作为前半段的头部分。

我的代码可能有一点唐氏，讲得也没有官方的好，所以我贴在这里，简单介绍一下，一些注释基本代表了我的想法，需要注意的只有一点，就是需要先翻转后面的节点，然后再和前面的节点拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 反转链表的递归实现
 * @param head 后面需要反转的链表的头节点
 * @param pre 已经完成反转的前半部分的最后一个节点
 * @return 反转完之后链表的头节点
 */
public static ListNode reverseListDFS(ListNode head,ListNode pre){
  	//判空
    if(null == head) return head;
    //定义递归终点，也就是最后一个节点，直接把它和它前面的那个节点拼起来然后返回
    if(null == head.next){
      head.next=pre;
      return head;
    }
  	//如果不是递归终点，这部分就需要理解一下
    else {
      	//首先是将后面部分翻转！
        ListNode res = reverseListDFS(head.next, head);
      	//然后将改节点的next改为pre，拼接起来，顺序一定不能错
        head.next = pre;
        return res;
    }
}

public ListNode reverseList(ListNode head) {
  	return reverseListDFS(head,null);
}

然后让我们来实现一下迭代的方式，迭代主要还是双指针的思路，其实相对而言思路比递归更容易理解一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 反转链表迭代实现
 * @param head 头指针
 * @return 反转完之后链表的头节点
 */
public static ListNode reverseListIter(ListNode head) {
    //判空
    if(null == head) return null;
    //定义双指针，这个定义是有技巧的，因为头节点的next要是null
    ListNode lst = null;
    ListNode pre = head;
    //依次设置前指针的next为后指针
    while(null != pre){
        ListNode tmp=pre.next;
        pre.next = lst;
        lst = pre;
        pre = tmp;
    }
    //当前指针为空时，后指针所指着的位置就是最后一个Node，也就是我们所需要的head
    return lst;
}

然后反转链表部分我们就基本讲完了，但是迭代这个部分的代码在后面我们还需要进行一点小小的修改，为什么呢，因为K个一组反转链表，链表的终点不是null，而是我们需要的终点是第K个节点。

接下来就是K个一组反转链表的任务，简单来说，我们只需要把任务拆成K个反转链表的子任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static void reverseSubList(ListNode head, ListNode last) {
    //判空
    if(null == head) return;
    //定义双指针
    ListNode lst = null;
    ListNode pre = head;
    //依次设置前指针的next为后指针
    while(last != lst){
        ListNode tmp = pre.next;
        pre.next = lst;
        lst = pre;
        pre = tmp;
    }
}

public ListNode reverseKGroup(ListNode head, int k) {
    //当k=1的时候，直接返回
    if(1 == k) return head;
    //为了统一以及便于找到头，我们定义一个伪头部，其实这是很常用的方法
    ListNode fake_head = new ListNode();
    fake_head.next=head;
    //如果k不等于1，接下来我们就需要定义一个节点，这个节点所需要做的事情就是找到每组的第K个节点
    ListNode findK = fake_head;
    ListNode lst_one = fake_head;
    int count = 0;
    //这里只需要判断findK是不是空，因为它一直走在其余两个交换位置的指针的前面
    while(null!=findK){
        //如果不是第K个，直接后移，不做处理
        if(count!=k){
            count++;
            findK=findK.next;
        }
        //如果是第K个
        else{
            //重置寻找循环
            count=0;
            //首先是获得子段的头，子段的尾就是findK
            ListNode child_head=lst_one.next;
            ListNode K_next=findK.next;
            //然后进行子段反转，这里会把它的头尾都断开，所以之后就需要重新拼接
            reverseSubList(child_head,findK);
            //然后将前面的子段和尾节点拼接
            lst_one.next=findK;
            //将头节点和后面的节点拼接
            child_head.next=K_next;
            //重置last_one和findK
            lst_one = child_head;
            findK = child_head;
        }
    }
    return fake_head.next;
}

我只能说，很优雅，但是还是建议大家看看官解，我写的很简陋。