剑指 Offer 24. 反转链表
/**
* 单链表的翻转
*
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
//设置新的节点
ListNode dumpy = new ListNode(-1);
dumpy.next = head;
ListNode pre = dumpy;
ListNode cur = head;
while (cur.next != null) {
ListNode future = cur.next;
cur.next = future.next;
future.next = pre.next;
pre.next = future;
}
return dumpy.next;
}
/**
* 单链表的翻转
*
* @param head
* @return
*/
public ListNode reverseList1(ListNode head) {
ListNode pre = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = pre;
pre = curr;
curr = next;
}
return pre;
}92. 反转链表 II
/**
* 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
*
* 说明:
* 1 ≤ m ≤ n ≤ 链表长度。
*/
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) return head;
ListNode dumpy = new ListNode(-1);
dumpy.next = head;
ListNode pre = dumpy;//第一段最后的一个节点
//找到第m个节点
for (int i = 1; i < m; i++) {
pre = pre.next;
}
ListNode cur = pre.next;
for (int i = m; i < n; i++) {
ListNode future = cur.next;
cur.next = future.next;
future.next = pre.next;
pre.next = future;
}
return dumpy.next;
}
148. 排序链表（单链表无序 不能使用其他的空间 要求使用的是的nlogn的时间复杂度）
/**
* 链表的实现有序排列
* 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
*/
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//使用快慢指针
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
//递归的去拆分
ListNode left = sortList(head);
ListNode right = sortList(tmp);
//合并链表
ListNode result = mergeTwoLists(left, right);
return result;
}
/**
* 链表和合并 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建一个新的链表
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
// 任一为空，直接连接另一条链表
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummyHead.next;
}剑指 Offer 25. 合并两个排序的链表
/**
* 链表和合并 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建一个新的链表
ListNode dummyHead = new ListNode(0);
ListNode cur = dummyHead;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
cur = cur.next;
l1 = l1.next;
} else {
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}
// 任一为空，直接连接另一条链表
if (l1 == null) {
cur.next = l2;
} else {
cur.next = l1;
}
return dummyHead.next;
}剑指 Offer 35. 复杂链表的复制
//创建HashMap集合
HashMap map = new HashMap();
Node cur=head;
//复制结点值 存放在map中
while(cur!=null){
//存储put:
map.put(cur,new Node(cur.val)); //顺序遍历，存储老结点和新结点(先存储新创建的结点值)
cur=cur.next;
}
//遍历原来的结果 获取指针
cur = head;
while(cur!=null){
//得到get:.value2,3
map.get(cur).next = map.get(cur.next); //新结点next指向同旧结点的next指向
map.get(cur).random = map.get(cur.random); //新结点random指向同旧结点的random指向
cur = cur.next;
}
//返回复制的链表
return map.get(head);剑指 Offer 36. 二叉搜索树与双向链表
/**
* Copyright (C), 2018-2020
* FileName: treeToDoublyList
* Author: xjl
* Date: 2020/8/12 16:51
* Description: 二叉树的与双相链表
*/
package LinkList;
/**
* 二叉树的变成一个双相链表
* 一：遍历的的方式
* 二：判断链表的尾部节点和遍历的当前的节点的关系
* 三：原来的二叉树指向是否需要改动
*/
public class treeToDoublyList {
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode() {
}
public TreeNode(int _val) {
val = _val;
}
public TreeNode(int _val, TreeNode _left, TreeNode _right) {
val = _val;
left = _left;
right = _right;
}
}
private TreeNode ans;//最终的双链表的头部
private TreeNode removeNode;//双向链表的尾部节点
private void dfs(TreeNode node, int flag) {
//flag 表示的是的第n+1层的节点的方向 0表示的第n+1层左孩子 1表示的是第n+1的右孩子
if (node != null) {
//遍历左子树
dfs(node.left, 0);
}
if (ans == null) {
ans = node;
removeNode = node;
} else {
//做好一般的处理 添加一个边、修改边
if (flag == 0) {
removeNode.right = node;//从尾部节点的引出一条指向当前的节点 也就是说创建一个从小到大的边
node.left = removeNode;//这行代码对于非root节点是没有影响的 主要是为了修改是的root的左孩子的
} else {
removeNode.right = node;//这行代码对于非root节点是没有影响的 主要是为了修改是的root的右边孩子的
node.left = removeNode;//从尾部节点的引出一条指向当前的节点 也就是说创建一个大到小的边
}
removeNode = node;//更新的双向链表的节点
}
if (node.right != null) {
dfs(node.right, 1);
}
}
public TreeNode treeToDoublyList(TreeNode root) {
if (root == null) {
return null;
}
ans = null;
removeNode = null;
dfs(root, 0);
return ans;
}
}
两个链表的第一个公共节点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//思路：双指针法。一个指针指向A链表，一个指向B链表。如果相遇则返回，否则没有交点。
//如果存在相交结点，那么pA和pB一定会相遇。
if(headA == null || headB == null) return null;
ListNode pA = headA,pB = headB;
while(pA != pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Stack stack1 = new Stack();
Stack stack2 = new Stack();
//链表入栈
while (headA != null) {
stack1.add(headA);
headA = headA.next;
}
while (headB != null) {
stack2.add(headB);
headB = headB.next;
}
//存结果
ListNode ans = null;
//遍历栈
while (!stack1.isEmpty() && !stack2.isEmpty()) {
if (stack1.peek()== stack2.peek()) {
ans = stack1.peek();
stack1.pop();
stack2.pop();
} else {
break;
}
}
return ans;
}面试题 02.06. 回文链表
/**
* Copyright (C), 2018-2020
* FileName: isPalindrome0206
* Author: xjl
* Date: 2020/8/12 20:18
* Description:
*/
package LinkList;
import org.junit.Test;
public class isPalindrome0206 {
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
/**
* 反转链表比较
*
* @param head
* @return
*/
public boolean isPalindrome1(ListNode head) {
// 使用快慢指针，慢指针在进行操作的时候，顺带的进行链表的翻转，在进行半个链表之间的比较
if (head == null) {
return true;
}
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode slow = dummyNode;
ListNode fast = dummyNode;
ListNode prev = null;
// 使用快慢指针找到链表的中间位置，并翻转慢指针前的链表
while (fast != null && fast.next != null) {
fast = fast.next.next;
// 链表翻转
ListNode temp = slow.next;
slow.next = prev;
prev = slow;
slow = temp;
}
ListNode rigth;
if (fast != null) {
// 不为空，表示链表size为偶数
// 0 -> 1 -> 2 -> 3, prev指向1，slow指向2，要比较prev与right，先确定位置1与2的val是不是一样的
if (slow.val != slow.next.val) {
return false;
}
// rigth从3开始
rigth = slow.next.next;
} else {
// 为空，表示链表size为奇数
// 0 -> 1 -> 2 -> 3 -> 4, prev指向1，slow指向2
// rigth从3开始
rigth = slow.next;
}
// 比较两个链表
while (prev != null && rigth != null) {
if (prev.val != rigth.val) {
return false;
}
prev = prev.next;
rigth = rigth.next;
}
return true;
}
/**
* 反转链表
*
* @param head
* @return
*/
public ListNode test11(ListNode head) {
ListNode dumpy = new ListNode(-1);
dumpy.next = head;
ListNode pre = dumpy;
ListNode curr = head;
while (curr.next != null) {
ListNode furtue = curr.next;
curr.next = furtue.next;
furtue.next = pre.next;
pre.next = furtue;
}
return dumpy.next;
}
public boolean isPalindrome3(ListNode head) {
if (head==null)return true;
String result1 = "";
ListNode curr = head;
while (curr != null) {
result1 += String.valueOf(curr.val);
curr = curr.next;
}
ListNode node = test11(head);
String result2 = "";
while (node != null) {
result2 += String.valueOf(node.val);
node = node.next;
}
return result1.equals(result2);
}
@Test
public void test() {
ListNode s1 = new ListNode(1);
boolean palindrome3 = isPalindrome3(s1);
System.out.println(palindrome3);
}
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
ListNode midNode = findMidNode(head);
ListNode secondHalfHead = reverseLinked(midNode.next);
ListNode curr1 = head;
ListNode curr2 = secondHalfHead;
boolean palindrome = true;
while(palindrome && curr2 != null){
if(curr1.val != curr2.val) palindrome = false;
curr1 = curr1.next;
curr2 = curr2.next;
}
return palindrome;
}
/* 反转链表 */
private ListNode reverseLinked(ListNode head){
ListNode cur = head;
ListNode prev = null;
while(cur != null){
ListNode nextTemp = cur.next;
cur.next = prev;
prev = cur;
cur = nextTemp;
}
return prev;
}
/* 快慢指针寻找中间节点 */
private ListNode findMidNode(ListNode head){
ListNode fast = head;
ListNode low = head;
while(fast.next != null && fast.next.next != null){
fast = fast.next.next;
low = low.next;
}
return low;
}
}
143. 重排链表
/**
* Copyright (C), 2018-2020
* FileName: reorderList
* Author: xjl
* Date: 2020/8/12 21:58
* Description: 143. 重排链表
*/
package LinkList;
import java.util.ArrayDeque;
import java.util.Deque;
public class reorderList {
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;
}
}
public void reorderList(ListNode head) {
if (head == null) {
return;
}
//设置一个栈空间
Deque stack = new ArrayDeque();
ListNode curr = head;
//将所有的节点都放置在栈中
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
curr=head;
ListNode stack_curr=new ListNode(Integer.MAX_VALUE);
while (curr.next!=stack_curr.next){
stack_curr=stack.poll();
stack_curr.next=curr.next;
curr.next=stack_curr;
curr=curr.next.next;
}
stack_curr.next=null;
}
}
