解题＞在线OJ(七)

1.移除链表

解题思路&＃xff1a;
1.首先&＃xff0c;如果head不为空并且值等于val&＃xff0c;就让head指针往下一个节点指&＃xff1b;
2.第二步&＃xff0c;此时判断 head是否为空&＃xff0c;这里的判空是有两种可能性的&＃xff0c;一个是head本来就是空的&＃xff0c;第二种可能性是链表中的节点值都等于这个val值&＃xff0c;如果为空&＃xff0c;直接返回head即可&＃xff1b;
3.当链表不为空的情况下&＃xff0c;定义两个节点&＃xff0c;一个指向head节点&＃xff08;preNode&＃xff09;&＃xff0c;一个指向head节点的下一个节点(node)&＃xff0c;进入循环&＃xff0c;如果node的值等于val&＃xff0c;则preNode.next&＃61;node.next;否则&＃xff0c;preNode&＃61;node;
4.返回head。

class Solution {public ListNode removeElements(ListNode head, int val) {while(head !&＃61;null && head.val&＃61;&＃61;val){head&＃61;head.next;}if(head&＃61;&＃61;null){return head;}ListNode preNode&＃61;head;ListNode node&＃61;head.next;while(node !&＃61; null){if(node.val&＃61;&＃61;val){preNode.next&＃61;node.next;}else{preNode&＃61;node;}node&＃61;node.next;}return head;}
}


2.反转链表

解题思路&＃xff1a;
首先&＃xff0c;判断head是否为空&＃xff1b;
其次&＃xff0c;定义preNode&＃xff0c;让这个节点指向null,然后&＃xff0c;定义node&＃xff0c;让这个节点指向head;
然后&＃xff0c;进入循环&＃xff0c;首先&＃xff0c;将node的下一个节点记录下来&＃xff0c;然后改变node的指针方向&＃xff0c;让其指向preNode,然后更新preNode的指向和node的指向&＃xff1b;
最后&＃xff0c;返回preNode。

class Solution {public ListNode reverseList(ListNode head) {if(head&＃61;&＃61;null){return null;}ListNode preNode&＃61;null;ListNode node&＃61;head;while(node!&＃61;null){ListNode nodeNext&＃61;node.next;node.next&＃61;preNode;preNode&＃61;node;node&＃61;nodeNext;}return preNode;}
}


3.链表的中间结点

解题思路&＃xff1a;
1.首先遍历整个链表&＃xff0c;计算出整个链表的长度&＃xff1b;
2.找出中间节点&＃xff0c;不论是偶数个节点还是奇数个节点&＃xff0c;中间节点是第几个节点的公式是:mid&＃61;count/2&＃43;1;
3.再次进入循环&＃xff0c;知道临时节点指向这个中间节点&＃xff1b;
4.返回这个临时节点。

class Solution {public ListNode middleNode(ListNode head) {ListNode node&＃61;head;int count&＃61;0;while(node!&＃61;null){count&＃43;&＃43;;node&＃61;node.next;}int mid&＃61;count/2&＃43;1;ListNode temp&＃61;head;for(int i&＃61;1;i<mid;i&＃43;&＃43;){temp&＃61;temp.next;}return temp;}
}


4.链表中倒数第k个结点

解题思路&＃xff1a;
定义两个指针&＃xff0c;一个快指针&＃xff0c;一个慢指针
1.让两个指针都指向head;
2.让快指针指到第k个节点&＃xff0c;从第0个节点(head)节点开始计算&＃xff0c;当然&＃xff0c;在这个过程中还需要保证快指针不会指到空,(这种情况是&＃xff1a;当k的值大于链表节点个数的时候)
3.当快指针指到第k个节点时,循环&＃xff0c;当快指针没有指向空的时候&＃xff0c;快指针和慢指针都往后移动&＃xff1b;
4.直到快指针指向空的时候&＃xff0c;此时&＃xff0c;返回慢指针对应的节点即可。

public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if(head&＃61;&＃61;null){return head;}ListNode fast&＃61;head;ListNode slow&＃61;head;for(int i&＃61;0;i<k;i&＃43;&＃43;){if(fast&＃61;&＃61;null){return null;}fast&＃61;fast.next;}while(fast!&＃61;null){slow&＃61;slow.next;fast&＃61;fast.next;}return slow;}}


5.合并两个有序链表

解题思路&＃xff1a;
1.判断两个链表是否为空&＃xff1b;
2.当两个链表都不为空的情况下&＃xff0c;遍历这两个链表&＃xff0c;定义一个新的头节点&＃xff0c;两个链表节点的值哪个小&＃xff0c;就让节点值小的节点接在新的头节点之后。
3.当某一个链表遍历完了之后&＃xff0c;将另一个链表剩余的节点全部都补充在新的头节点之后。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1&＃61;&＃61;null && list2&＃61;&＃61;null){return null;}if(list1&＃61;&＃61;null && list2!&＃61;null){return list2;}if(list1!&＃61;null && list2&＃61;&＃61;null){return list1;}ListNode node&＃61;new ListNode(-1);ListNode head&＃61;node;ListNode temp1&＃61;list1;ListNode temp2&＃61;list2;while(temp1!&＃61;null && temp2!&＃61;null){if(temp1.val<temp2.val){head.next&＃61;temp1;temp1&＃61;temp1.next;}else{head.next&＃61;temp2;temp2&＃61;temp2.next;}head&＃61;head.next;}while(temp1!&＃61;null){head.next&＃61;temp1;temp1&＃61;temp1.next;head&＃61;head.next;}while(temp2!&＃61;null){head.next&＃61;temp2;temp2&＃61;temp2.next;head&＃61;head.next;}return node.next;}
}

6.链表分割

解题思路&＃xff1a;
创建四个节点&＃xff0c;形成两个链表&＃xff0c;一个链表专门记录比x小的节点&＃xff0c;一个链表专门记录比x大的节点&＃xff1b;
1.比x小的节点链表&＃xff1a;创建两个节点,一个是头&＃xff0c;一个是尾&＃xff0c;由尾部往后增加节点&＃xff1b;
2.比x大的节点链表&＃xff1a;创建两个节点&＃xff0c;一个是头&＃xff0c;一个是尾&＃xff0c;由尾部往后增加节点&＃xff1b;
3.当遍历完原来链表的时候&＃xff0c;将小的节点链表的尾部 连上 大的节点链表的头部&＃xff0c;并且将大的节点尾部指向null;
4.返回小的节点链表头部的下一个节点&＃xff1b;

public class Partition {public ListNode partition(ListNode pHead, int x) {// write code hereListNode bigHead&＃61;new ListNode(-1);ListNode smallHead&＃61;new ListNode(-1);ListNode smallTail&＃61;smallHead;ListNode bigTail&＃61;bigHead;while(pHead!&＃61;null){if(pHead.val<x){smallTail.next&＃61;pHead;smallTail&＃61;smallTail.next;}else{bigTail.next&＃61;pHead;bigTail&＃61;bigTail.next;}pHead&＃61;pHead.next;}bigTail.next&＃61;null;smallTail.next&＃61;bigHead.next;return smallHead.next;}
}


7.删除链表中重复的节点

解题思路&＃xff1a;
定义三个节点变量&＃xff1b;
当cur.val&＃61;&＃61;cur.next.val&＃xff0c;进入循环&＃xff0c;cur指向下一个节点&＃xff1b;
直到cur的节点值不等于cur.next的节点值时&＃xff0c;此时&＃xff0c;将cur指向下一个节点&＃xff1b;
此时&＃xff0c;需要再次判断&＃xff0c;以防出现这种情况:1->2->2->3->3,当cur.val等于cur.next.val的时候&＃xff0c;跳出本次循环&＃xff0c;目的是 继续执行上一层循环判断&＃xff1b;
直至找到没有重复节点&＃xff0c;此时pre.next&＃61;cur;
最后&＃xff0c;返回root.next。

public class Solution {public static ListNode deleteDuplication(ListNode pHead) {if(pHead&＃61;&＃61;null || pHead.next&＃61;&＃61;null){return pHead;}ListNode root&＃61;new ListNode(-1);root.next&＃61;pHead;ListNode pre&＃61;root;ListNode cur&＃61;root;while(cur!&＃61;null){while(cur!&＃61;null&& cur.next!&＃61;null && cur.val&＃61;&＃61;cur.next.val){cur&＃61;cur.next;}cur&＃61;cur.next;if(cur!&＃61;null && cur.next!&＃61;null && cur.val&＃61;&＃61;cur.next.val){continue;}pre.next&＃61;cur;pre&＃61;pre.next;}return root.next;}
}


8.链表的回文结构

解题思路&＃xff1a;
首先&＃xff0c;定义两个节点&＃xff0c;一个快节点&＃xff0c;一个慢节点&＃xff1b;
1.找到链表的中间节点&＃xff0c;快节点一次走两步&＃xff0c;慢节点一次走一步&＃xff0c;直到fast指向null或者fast.next指向null&＃xff0c;此时&＃xff0c;slow指向的节点就是链表的中间节点&＃xff1b;
2.此时&＃xff0c;将快指针移到slow的下一个节点&＃xff0c;开始循环&＃xff0c;将中间节点的之后链表&＃xff0c;进行链表反转&＃xff1b;
3.此时&＃xff0c;slow指向最后一个节点&＃xff0c;此刻&＃xff0c;A节点开始往后遍历&＃xff0c;slow开始往前遍历&＃xff0c;判断&＃xff0c;A节点对应的val值是否等于slow节点对应的val;
总的来说&＃xff0c;就是&＃xff1a;找中间节点---->反转后半部分链表----->前后一起往中间遍历&＃xff0c;比较每次两端拿到的值是否相等。

public class PalindromeList {public static boolean chkPalindrome(ListNode A) {// write code hereListNode fast&＃61;A;ListNode slow&＃61;A;//找链表的中间节点&＃xff0c;fast一次走两步&＃xff0c;slow一次走一步while(fast!&＃61;null && fast.next!&＃61;null){fast&＃61;fast.next.next;slow&＃61;slow.next;}//此时slow指的就是中间节点&＃xff0c;现在需要进行对链表的后半部分进行链表反转fast&＃61;slow.next;while(fast!&＃61;null) {ListNode fastNext &＃61; fast.next;fast.next &＃61; slow;slow &＃61; fast;fast &＃61; fastNext;}while(slow!&＃61;A){if(slow.val!&＃61;A.val){return false;}if(A.next&＃61;&＃61;slow){return true;}if(A.val&＃61;&＃61;slow.val){A&＃61;A.next;slow&＃61;slow.next;}}return true;}
}


9.环形链表

链接: https://leetcode-cn.com/problems/linked-list-cycle-ii/description/.

解题思路&＃xff1a;
定义两个节点&＃xff0c;一个快节点&＃xff0c;一个慢节点&＃xff1b;
快节点一次走两步&＃xff0c;慢节点一次走一步&＃xff0c;当两个节点相遇的时候&＃xff0c;就证明这个链表是一个环形链表&＃xff0c;否则&＃xff0c;就不是环形链表&＃xff1b;
其&＃xff0c;主要的循环条件是&＃xff1a;fast!&＃61;null && fast.next!&＃61;null。

public class Solution {public static boolean hasCycle(ListNode head) {if(head&＃61;&＃61;null || head.next&＃61;&＃61;null){return false;}ListNode fast&＃61;head;ListNode slow&＃61;head;while(fast!&＃61;null && fast.next!&＃61;null){fast&＃61;fast.next.next;slow&＃61;slow.next;if(fast&＃61;&＃61;slow){return true;}}return false;}
}


10.环形链表II

链接: https://leetcode-cn.com/problems/linked-list-cycle-ii/description/.

解题思路&＃xff1a;
创建快慢指针&＃xff1b;
快指针一次走两步&＃xff0c;慢指针一次走一步&＃xff0c;直到找到他们的相遇点&＃xff1b;
找到快慢指针的相遇点之后&＃xff0c;退出循环&＃xff1b;
定义一个新的节点&＃xff0c;指向头节点&＃xff0c;现在让这个新结点开始往后走&＃xff0c;慢指针也往后走&＃xff0c;直到两个点相遇&＃xff0c;两个点相遇的点就是入环的第一个节点。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast&＃61;head;ListNode slow&＃61;head;while(true){if(fast&＃61;&＃61;null || fast.next&＃61;&＃61;null){return null;}fast&＃61;fast.next.next;slow&＃61;slow.next;if(fast&＃61;&＃61;slow){break;}}ListNode third&＃61;head;while(third!&＃61;slow){slow&＃61;slow.next;third&＃61;third.next;}return third;}
}