将单向链表按照目标值value 划分成左边小,中间等,右边大的形式
例如 1 -> 3 -> 5-> 3 -> 7 按照value = 3划分 1-> 3-> 3 -> 5 -> 7
解题思路:给定值为 value
-
用6个变量,分别表示 小于value 的Head
sH
,小于 value 的TailsT
,等于value 的HeadeH
,等于value 的TaileT
,大于value 的HeadhH
, 大于value的TailhT
-
遍历 list链表
-
对于每一个值与value 做比较
-
在某一个区间内 ,例如 大于区间
-
- 如果 hH == null 说明 大于区间还没有数字,hH 和hT 全部指向当前这个节点
- 如果hH != null 说明已经有值了 , 移动 尾部hT 节点指向当前的节点
-
最后把三个区域进行连接即可
要点:
- 每一个区域组成的都是一个链表 ,从head 到tail
- 每个区域添加节点的时候,要把当前节点的 next 节点变为null ,否则当前节点的next 节点会影响链表的结果 例如 1 -> 2-> 3 value = 3 在 1节点的时候 ,1要放在小于区域, 如果不把 next节点置 null ,那么 sH 和 sT 等于的就是 1 -> 2-> 3 ,而不是 1
- next置空之前,要记录next 节点,要不然next节点会丢失
- 最后连接的时候,有可能某一个区域没有节点(尾节点为null),这是跳过这个区域连接即可
public static Node getPartitionNode(Node head, int value) {Node sH = null;Node sT = null;Node eH = null;Node eT = null;Node hH = null;Node hT = null;Node next = null;while (head != null) {next = head.next;head.next = null;if (head.value < value) {if (sH == null) {sH = head;sT = head;} else {sT.next = head;sT = sT.next;}} else if (head.value == value) {if (eH == null) {eH = head;eT = head;} else {eT.next = head;eT = eT.next;}} else {if (hH == null) {hH = head;hT = head;} else {hT.next = head;hT = hT.next;}}head = next;}if (sT != null) {sT.next = eH;// eT 如果不是空 用 eT去连接 ,是空 用sT 去连eT = eT == null ? sT : eT;}if (eT != null) {eT.next = hH;}return sH == null ? (eH == null ? hH : eH) : sH;
}
给定一个单链表,判断单链表的值是否是回文结构
可以将所有数存到栈中(得到链表逆序),在遍历链表(链表正序),每一次栈弹出一个,验证链表的正序和逆序是否相等 这个解法不好,因为使用了一个栈的额外空间
- 通过快慢指针,快指针走到链表结尾时,慢指针到中心点位置
- 通过慢指针和快指针逆序后半部分链表的指针形成一个 1 -> 2 -> 3 <- 3<- 2 <- 1 的链表形式
- 从链表两端分别遍历,每个值比较判断是否相等
- 最后链表重新恢复原来的结构
只是用了有限几个变量,空间复杂度从 O(N) 变为 O(1)
要点:
- 找中点时,有可能快指针指向的不是最后一个节点,是倒数第二个,但是无所谓,只要中点找到了就可以
- 找到中点后,要记住中点的下一个节点,根据中点切割成两个链表
找链表中点图示
public static boolean isPalindromeList(Node head){if (head == null || head.next == null){return true;}Node low = head;Node fast = head;while (fast.next != null && fast.next.next != null){fast = fast.next.next;low = low.next;}// 分隔开个链表fast = low.next;low.next = null;Node temp ;while (fast != null){temp = fast.next;// 直接使用low 相当于pre节点fast.next = low;low = fast;fast = temp;}temp = low; //保存下最后一个节点,最后链表要还原fast = head;boolean res = true;while (low != null && fast != null){if (low.value != fast.value){res = false;break;}low = low.next;fast = fast.next;}// 还原fast = temp;low = null;while (fast != null){temp = fast.next;fast.next = low;low = fast;fast = temp;}return res;
}
public static boolean isPalindromeListForStack(Node head){if (head == null || head.next == null){return true;}Stack<Integer> stack = new Stack<>();Node cur = head;while (cur != null){stack.add(cur.value);cur = cur.next;}boolean res = true;cur = head;while (!stack.isEmpty() && cur != null){if(cur.value != stack.pop()){res = false;break;}cur = cur.next;}return res;
}