public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
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 reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
ListNode next=null;
while(cur!=null)
{
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) {
return false;
}
if (currentNode.val != frontPointer.val) {
return false;
}
frontPointer = frontPointer.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
frontPointer = head;
return recursivelyCheck(head);
}
//快慢指针
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
public ListNode detectCycle(ListNode head) {
List<ListNode> list = new ArrayList();
ListNode th = head;
ListNode result = null;
while (th != null) {
if (!list.contains(th)) {
list.add(th);
th = th.next;
} else {
result = list.get(list.indexOf(th));
break;
}
}
return result;
}
//递归
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
//拼接
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev.next = l1 == null ? l2 : l1;
return prehead.next;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
ListNode cur = pre;
int carry = 0;
while(l1 != null || l2 != null) {
int x = l1 == null ? 0 : l1.val;
int y = l2 == null ? 0 : l2.val;
int sum = x + y + carry;
carry = sum / 10;
sum = sum % 10;
cur.next = new ListNode(sum);
cur = cur.next;
if(l1 != null)
l1 = l1.next;
if(l2 != null)
l2 = l2.next;
}
if(carry == 1) {
cur.next = new ListNode(carry);
}
return pre.next;
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = new ListNode(0);
pre.next = head;
ListNode start = pre, end = pre;
while (n != 0) {
start = start.next;
n--;
}
while (start.next != null) {
start = start.next;
end = end.next;
}
end.next = end.next.next;
return pre.next;
}
public ListNode swapPairs(ListNode head) {
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode cur = pre;
while (cur.next != null && cur.next.next != null) {
ListNode first = cur.next;
ListNode second = cur.next.next;
cur.next = second;
first.next = second.next;
second.next = first;
cur = first;
}
return pre.next;
}
public ListNode reverseKGroup(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;
}
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 h = new ListNode(0);
ListNode res = h;
while (left != null && right != null) {
if (left.val < right.val) {
h.next = left;
left = left.next;
} else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
折半查找
private int getFind(int[] arry, int tag) {
int left = 0;
int right = arry.length - 1;
while (left != right) {
int mind = left + (right - left) / 2;
if (arry[mind] == tag)
return mind;
else if (arry[mind] < tag) {
left=mind+1;
} else {
right=mind-1;
}
}
return -1;
}
链表内指定区间反转
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
//设置虚拟头节点
ListNode dummy =new ListNode(-1);
dummy.next=head;
ListNode pre=dummy;
//将pre指针移动到m前一个位置
for(int i=0;i<m-1;i++){
pre=pre.next;
}
//获取m位置
ListNode cur=pre.next;
ListNode next;
for(int i=0;i<n-m;i++){
next=cur.next;
cur.next=next.next;
//注意这里不能是next.next=cur,因为cur一直指的是最开始时m位置的节点
next.next=pre.next;
pre.next=next;
}
return dummy.next;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode tail = head;
//获得每个反转组的最后一个节点
for(int i = 0; i < k; i++){
if(tail == null){
return head;
}
tail = tail.next;
}
ListNode pre = null;
ListNode cur = head;
while(cur != tail){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
head.next = reverseKGroup(tail,k);
return pre;
}
链表删除某个节点
public ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
return head.next;
}
ListNode prev = head;
ListNode curr = head.next;
while (curr != null) {
if (curr.val == val) {
prev.next = curr.next;
break;
}
prev = curr;
curr = curr.next;
}
return head;
}
//递归
public ListNode deleteNode(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
return head.next;
}
head.next = deleteNode(head.next, val);
return head;
}
两个队列实现一个栈
import java.util.LinkedList;
import java.util.Queue;
public class StackUsingTwoQueues {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public StackUsingTwoQueues() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int item) {
if (!queue1.isEmpty()) {
queue1.offer(item);
} else if (!queue2.isEmpty()) {
queue2.offer(item);
} else {
queue1.offer(item);
}
}
public Integer pop() {
if (!queue1.isEmpty()) {
while (queue1.size() > 1) {
queue2.offer(queue1.poll());
}
return queue1.poll();
} else if (!queue2.isEmpty()) {
while (queue2.size() > 1) {
queue1.offer(queue2.poll());
}
return queue2.poll();
}
return null; // 栈为空
}
public Integer peek() {
if (!queue1.isEmpty()) {
return queue1.peek();
} else if (!queue2.isEmpty()) {
return queue2.peek();
}
return null; // 栈为空
}
public boolean isEmpty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}
