public class TestClass {
public static void main(String[] agrs) {
List<ListNode> listNodes = new ArrayList<>();
}
//快速排序
public void quickSort(int arr[], int head, int tail) {
if (head > tail) {
return;
}
int result = arr[head];
int i = head;
int j = tail;
while (i < j) {
while (arr[i] <= result && i < j) {
i++;
}
while (arr[j] >= result && j > i) {
j--;
}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
if (i == j) {
arr[head] = arr[i];
arr[i] = result;
}
quickSort(arr, head, i - 1);
quickSort(arr, i + 1, tail);
}
//刪除鏈表第N個(gè)節(jié)點(diǎn)
public ListNode deleteNNode(ListNode mTreeNode, int n) {
ListNode head = new ListNode(0);
head.next = mTreeNode;
ListNode first = head;
ListNode second = head;
for (int i = 0; i < n; i++) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return head.next;
}
//刪除鏈表第N個(gè)節(jié)點(diǎn)
public ListNode deleteN2Node(ListNode mTreeNode, int n) {
ListNode head = new ListNode(0);
head.next = mTreeNode;
ListNode first = head;
ListNode second = head;
int count = 0;
while (first != null) {
first = first.next;
count++;
}
for (int i = 0; i < count - n; i++) {
second = second.next;
}
second.next = second.next.next;
return head;
}
//合并兩個(gè)鏈表
public ListNode conbineTreeNode(ListNode first, ListNode second) {
ListNode treeNode = new ListNode(0);
ListNode temp = treeNode;
while (first != null && second != null) {
int val = first.val;
int result = second.val;
if (val < result) {
temp.next = first;
first = first.next;
} else {
temp.next = second;
second = second.next;
}
temp = temp.next;
}
if (first == null) {
temp.next = second;
} else {
temp.next = first;
}
return treeNode.next;
}
//兩兩交換鏈表節(jié)點(diǎn) 1-2-3-4-5-6 2-1-4-3-6-5 遞歸思想
public ListNode changeTwoNodeByRec(ListNode mTreeNode) {
if (mTreeNode == null && mTreeNode.next == null) {
return mTreeNode;
}
ListNode node = mTreeNode.next;
mTreeNode.next = changeTwoNodeByRec(node.next);
node.next = mTreeNode;
return mTreeNode;
}
//旋轉(zhuǎn)單鏈表 1-2-3-4 4-3-2-1
public ListNode reverseTreeNode(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode tmp = head.next;
head.next = prev;
prev = head;
head = tmp;
}
return prev;
}
//遞歸旋轉(zhuǎn)單鏈表
public ListNode reverseTreeNodeByRec(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode treeNode = reverseTreeNodeByRec(head.next);
head.next.next = head;
head.next = null;
return treeNode;
}
//鏈表向右移動(dòng)n個(gè)節(jié)點(diǎn),先閉環(huán)返十，再斷節(jié)點(diǎn) 1-2-3-4 n = 2 --------> 3-4-1-2
public ListNode removeTreeNode(ListNode head, int n) {
//先整體閉合成環(huán)
ListNode node = head;
int count = 1;
while (node.next != null) {
node = node.next;
count++;
}
node.next = head;
ListNode tail = head;
for (int i = 0; i < n - n % count - 1; i++) {
tail = tail.next;
}
ListNode newHead = tail.next;
tail.next = null;
return newHead;
}
//刪除鏈表中的連續(xù)重復(fù)節(jié)點(diǎn) 1-2-3-3 1-2
public ListNode deleteDucliteNode(ListNode head) {
ListNode dump = new ListNode(0);
dump.next = head;
ListNode cur = dump;
while (cur != null && cur.next != null) {
ListNode temp = cur.next;
if (temp.next != null && temp.val == temp.next.val) {
ListNode end = temp.next;
while (temp.next != null && end.val == end.next.val) {
end = end.next;
}
cur.next = end.next;
} else {
cur = cur.next;
}
}
return dump.next;
}
//分割兩個(gè)鏈表 1-5-4-6-3-2 n =3 1-2-5-4-6-3
public ListNode divideListNode(ListNode head, int n) {
ListNode first = new ListNode(0);
ListNode dump = first;
ListNode second = new ListNode(0);
ListNode cur = second;
while (head != null) {
if (head.val >= n) {
cur.next = head;
cur = cur.next;
cur.next = null;
} else {
dump.next = head;
dump = dump.next;
dump.next = null;
}
head = head.next;
}
cur.next = second.next;
return first.next;
}
//反轉(zhuǎn)鏈表 m,n 1-2-3-4-5 n=2 m=4 1-4-3-2-5
//todo 未解決
public ListNode reverseListNode(ListNode head, int n, int m) {
if (m <= n) {
return head;
}
ListNode dump = new ListNode(0);
dump.next = head;
ListNode cur = dump;
for (int i = 0; i < n; i++) {
cur = cur.next;
}
head = cur.next;
for (int i = n; i < m; i++) {
ListNode nex = head.next;
head.next = nex.next;//2-4
nex.next = cur.next;//3-2
cur.next = nex;//1-2
}
return dump.next;
}
//有序鏈表轉(zhuǎn)二叉樹
public TreeNode listToTree(ListNode head) {
if (head == null) {
return new TreeNode(0);
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = listToTree(head);
root.right = listToTree(slow.next);
return root;
}
//二叉樹轉(zhuǎn)鏈表 https://blog.csdn.net/thousa_ho/article/details/77961918
public void flatten(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
flatten(root.left);
}
if (root.right != null) {
flatten(root.right);
}
TreeNode treeNode = root.right;
root.right = root.left;
root.left = null;
while (root.right != null) {
root = root.right;
}
root.right = treeNode;
}
//判斷鏈表是否回環(huán)
public boolean isCircleList(ListNode mListNode) {
ListNode fast = mListNode;
ListNode slow = mListNode;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
//重排鏈表 1-2-3-4-5 1-5-2-4-3
public void orderList(ListNode head) {
//找到中心點(diǎn)鳞青，反轉(zhuǎn)后續(xù)鏈表，向前面鏈表中插入
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode end = slow.next;
ListNode dump = end;
slow.next = null;
ListNode prev = null;
//1-2-3-4
while (dump != null) {
dump.next = prev;
prev = dump;
dump = dump.next;
}
ListNode cur = head;
while (cur != null && prev != null) {
ListNode nextF = cur.next;
ListNode nextE = prev.next;
cur.next = prev;
prev.next = cur.next;
cur = nextF;
prev = nextE;
}
}
//鏈表插入排序 1-6-2-4 1-2-4-6;
public ListNode insertList(ListNode head) {
ListNode dummy = new ListNode(0), pre;
dummy.next = head;
while (head != null && head.next != null) {
if (head.val <= head.next.val) {
head = head.next;
continue;
}
pre = dummy;
while (pre.next.val < head.next.val) pre = pre.next;
ListNode curr = head.next;
head.next = curr.next;
curr.next = pre.next;
pre.next = curr;
}
return dummy.next;
}
//排序鏈表,類似歸并排序的用法
public ListNode sortListByCombine(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode end = slow.next;
slow.next = null;
ListNode l1 = sortListByCombine(head);
ListNode l2 = sortListByCombine(end);
return conbineTreeNode(l1, l2);
}
//判斷是否為回文鏈表
public boolean isCircleList2(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode end = slow.next;
slow.next = null;
ListNode pre = null;
//1-2-3
while (end != null) {
end.next = pre;
end = end.next;
pre = end;
}
while (head != null && pre != null) {
if (head.val != pre.val) {
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
/**
* 樹系列相關(guān)題目
*/
//判斷兩個(gè)相同的樹
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p==null&&q==null){
return true;
}
if (p!=null&&q!=null&&p.val==q.val){
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
}else {
return false;
}
}
//判斷是否為對稱二叉樹
public boolean isMirrorTreeNode(TreeNode l1,TreeNode l2){
if (l1==null&&l2==null){
return true;
}
if (l1==null||l2==null){
return false;
}
return l1.val==l2.val&&isMirrorTreeNode(l1.left,l2.right)&&isMirrorTreeNode(l1.right,l2.left);
}
//二叉樹的層次遍歷
public List<List<Integer>> levelOrder(TreeNode head){
List<List<Integer>> mList = new ArrayList<>();
Queue<TreeNode> mQueue = new ArrayDeque<>();
mQueue.add(head);
while (!mQueue.isEmpty()){
List<Integer> list = new ArrayList<>();
for (int i = 0; i < mQueue.size(); i++) {
TreeNode poll = mQueue.poll();
list.add(poll.val);
if (poll.left!=null){
mQueue.offer(poll.left);
}
if (poll.right!=null){
mQueue.offer(poll.right);
}
}
mList.add(list);
}
return mList;
}
//鋸齒二叉樹遍歷
public List<List<Integer>> zigzagLevelOrder(TreeNode head){
List<List<Integer>> mList = new ArrayList<>();
Queue<TreeNode> mQueue = new ArrayDeque<>();
mQueue.add(head);
boolean isReverse = true;
while (!mQueue.isEmpty()){
List<Integer> list = new ArrayList<>();
for (int i = 0; i < mQueue.size(); i++) {
TreeNode poll = mQueue.poll();
list.add(poll.val);
if (isReverse){
if (poll.left!=null){
mQueue.offer(poll.left);
}
if (poll.right!=null){
mQueue.offer(poll.right);
}
}else{
if (poll.right!=null){
mQueue.offer(poll.right);
}
if (poll.left!=null){
mQueue.offer(poll.left);
}
}
}
isReverse = !isReverse;
mList.add(list);
}
return mList;
}
//獲取樹的最大深度
public int maxDepth(TreeNode root){
return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
//重建二叉樹,通過先序和中序 [3,9,20,15,7] [9,3,15,20,7]
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null || preorder.length==0){
return null;
}
return buildCore(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
}
private TreeNode buildCore(int[] preorder,int preSt,int preEnd,int[] inorder,int inSt,int inEnd){
//前序遍歷第一個(gè)節(jié)點(diǎn)是根節(jié)點(diǎn)
int rootValue = preorder[preSt];
TreeNode root = new TreeNode(rootValue);
//前序序列只有根節(jié)點(diǎn)
if(preSt == preEnd){
return root;
}
//遍歷中序序列咆蒿，找到根節(jié)點(diǎn)的位置
int rootInorder = inSt;
while(inorder[rootInorder]!=rootValue&&rootInorder<=inEnd){
rootInorder++;
}
//左子樹的長度
int leftLength = rootInorder - inSt;
//前序序列中左子樹的最后一個(gè)節(jié)點(diǎn)
int leftPreEnd = preSt + leftLength;
//左子樹非空
if(leftLength>0){
//重建左子樹
root.left = buildCore(preorder,preSt+1,leftPreEnd,inorder,inSt,inEnd);
}
//右子樹非空
if(leftLength < preEnd - preSt){
//重建右子樹
root.right = buildCore(preorder,leftPreEnd +1,preEnd,inorder,rootInorder+1,inEnd);
}
return root;
}
//有序列表轉(zhuǎn)成二叉樹
public TreeNode sortedArrayToBST(int[] nums) {
// 左右等分建立左右子樹久窟，中間節(jié)點(diǎn)作為子樹根節(jié)點(diǎn)秩冈，遞歸該過程
return nums == null ? null : buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(int[] nums, int l, int r) {
if (l > r) {
return null;
}
int m = l + (r - l) / 2;
TreeNode root = new TreeNode(nums[m]);
root.left = buildTree(nums, l, m - 1);
root.right = buildTree(nums, m + 1, r);
return root;
}
class ListNode {
int val;
ListNode next;
public ListNode(int mVal) {
this.val = mVal;
}
}
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
}
leetcode
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門租漂，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人颊糜，你說我怎么就攤上這事哩治。” “怎么了衬鱼？”我有些...
- 文/不壞的土叔 我叫張陵业筏，是天一觀的道長。 經(jīng)常有香客問我鸟赫，道長蒜胖，這世上最難降的妖魔是什么？ 我笑而不...
- 正文 為了忘掉前任抛蚤，我火速辦了婚禮台谢，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘岁经。我一直安慰自己朋沮，他們只是感情好，可當(dāng)我...
- 文/花漫 我一把揭開白布蒿偎。 她就那樣靜靜地躺著朽们，像睡著了一般。 火紅的嫁衣襯著肌膚如雪诉位。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼瞳筏，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了牡昆？” 一聲冷哼從身側(cè)響起姚炕，我...
- 序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后柱宦，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體些椒，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年掸刊，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了免糕。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
- 正文 年R本政府宣布，位于F島的核電站试吁，受9級特大地震影響棺棵，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜熄捍，卻給世界環(huán)境...
- 文/蒙蒙 一烛恤、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧余耽，春花似錦疗垛、人聲如沸赋除。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽屡贺。三九已至，卻和暖如春蚁趁，著一層夾襖步出監(jiān)牢的瞬間据途，已是汗流浹背。 一陣腳步聲響...
- 正文 我出身青樓冀续，卻偏偏與公主長得像琼讽，于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子洪唐，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- Leetcode 141 與 Leetcode 142 題類似钻蹬，Leetcode 141 為判斷鏈表是否有環(huán)，而L...
- 把兩道比較難的Backtracking的類似題放到一起凭需，總結(jié)一下格式问欠。 兩道題的具體講解參考youtube：htt...
- 參考：http://www.cnblogs.com/grandyang/p/5999050.html 這兩道題很像...
- TrieNode的建立盡量用haspmap來做肝匆，而不是array[256]。這樣省空間溅潜，而且可以查找非字母(相比T...
- 刷題質(zhì)量+刷題數(shù)量=Offer 面試遇到的問題： 明明刷過這道題术唬，面試被問依然無法100%bug free寫出來？...
