第一题：反转链表
题目描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0\leq n\leq10000≤n≤1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
示例
输入： {1,2,3}
返回值： {3,2,1}
输入： {}
返回值： {}
空链表则输出空
题解
import java.util.Stack; public class Solution { public ListNode ReverseList(ListNode head) { Stack<ListNode> stack= new Stack<>(); //把链表节点全部摘掉放到栈中 while (head != null) { stack.push(head); head = head.next; } if (stack.isEmpty()) return null; ListNode node = stack.pop(); ListNode dummy = node; //栈中的结点全部出栈，然后重新连成一个新的链表 while (!stack.isEmpty()) { ListNode tempNode = stack.pop(); node.next = tempNode; node = node.next; } //最后一个结点就是反转前的头结点，一定要让他的next //等于空，否则会构成环 node.next = null; return dummy; } }
第二题：链表内指定区间反转
题目描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.
数据范围： 链表长度 0 < size \le 10000<size≤1000，0 < m \le n \le size0<m≤n≤size，链表中每个节点的值满足 |val| \le 1000∣val∣≤1000
要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n)
进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)
示例
输入： {1,2,3,4,5},2,4
返回值： {1,4,3,2,5}
输入： {5},1,1
返回值： {5}
题解
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ // 解法一：双指针(两次遍历) //说明：方便理解，以下注释中将用left，right分别代替m,n节点 public ListNode reverseBetween (ListNode head, int m, int n) { //设置虚拟头节点 ListNode dummyNode = new ListNode(-1); dummyNode.next = head; ListNode pre = dummyNode; //1.走left-1步到left的前一个节点 for(int i=0;i<m-1;i++){ pre = pre.next; } //2.走roght-left+1步到right节点 ListNode rigthNode = pre; for(int i=0;i<n-m+1;i++){ rigthNode = rigthNode.next; } //3.截取出一个子链表 ListNode leftNode = pre.next; ListNode cur = rigthNode.next; //4.切断链接 pre.next=null; rigthNode.next=null; //5.反转局部链表 reverseLinkedList(leftNode); //6.接回原来的链表 pre.next = rigthNode; leftNode.next = cur; return dummyNode.next; } //反转局部链表 private void reverseLinkedList(ListNode head){ ListNode pre = null; ListNode cur = head; while(cur!=null){ //Cur_next 指向cur节点的下一个节点 ListNode Cur_next = cur.next; cur.next = pre; pre = cur; cur = Cur_next ; } } }
第三题：链表中的节点每k个一组翻转
题目描述
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
数据范围： \ 0 \le n \le 2000 0≤n≤2000 ， 1 \le k \le 20001≤k≤2000 ，链表中每个元素都满足 0 \le val \le 10000≤val≤1000
要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
例如：
给定的链表是 1\to2\to3\to4\to51→2→3→4→5
对于 k = 2k=2 , 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5
对于 k = 3k=3 , 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5
示例
输入： {1,2,3,4,5},2
返回值： {2,1,4,3,5}
输入： {},1
返回值： {}
题解
import java.util.*; public class Solution { public ListNode reverseKGroup (ListNode head, int k) { //找到每次翻转的尾部 ListNode tail = head; //遍历k次到尾部 for(int i = 0; i < k; i++){ //如果不足k到了链表尾，直接返回，不翻转 if(tail == null) return head; tail = tail.next; } //翻转时需要的前序和当前节点 ListNode pre = null; ListNode cur = head; //在到达当前段尾节点前 while(cur != tail){ //翻转 ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } //当前尾指向下一段要翻转的链表 head.next = reverseKGroup(tail, k); return pre; } }
