LeetCode奇偶链表
思路，两个指针，分别标注奇数节点与偶数节点
/*** Definition for singly-linked list.* 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; }* }*/class Solution {public ListNode oddEvenList(ListNode head) {if(head == null|| head.next == null)return head;ListNode oddHead = head;ListNode oddCur = oddHead;ListNode evenHead = head.next;ListNode evenCur = evenHead;while(evenCur != null&& evenCur.next != null){oddCur.next = oddCur.next.next;evenCur.next = evenCur.next.next;oddCur = oddCur.next;evenCur = evenCur.next;}oddCur.next = evenHead;return oddHead;}}
LeetCode82 删除链表中的重复元素 重复的全删除
双指针，cur不断前移，并且判断与cur.next.val的关系，相同就前移，判断pre.next是否等于cur不等证明中间有重复值直接删除就行pre.next = cur.next
/*** Definition for singly-linked list.* 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; }* }*/class Solution {public ListNode deleteDuplicates(ListNode head) {if(head == null|| head.next == null)return head;ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;ListNode cur = head;while(cur != null){while(cur.next != null&& cur.val == cur.next.val){cur = cur.next;}if(pre.next == cur){pre = pre.next;}else{pre.next = cur.next;}cur = cur.next;}return dummy.next;}}
LeetCode 83 删除链表重复元素，只保留一个
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null|| head.next == null)
return head;
ListNode cur = head;
while(cur.next != null&& cur != null){
if(cur.val == cur.next.val)
cur.next = cur.next.next;
else
cur = cur.next;
}
return head;
}
}
LeetCode92 反转链表
反转局部范围内的链表，头插法
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for(int i = 0; i < left-1; i++){
pre = pre.next;
}
ListNode cur = pre.next;
for(int i = 0; i < right - left; i++){
ListNode temp = cur.next;
cur.next = temp.next;
temp.next = pre.next;
pre.next = temp;
}
return dummy.next;
}
}
LeetCode86 分隔链表
给了个x小于x的在前面大于在后面，四指针，小头小尾，大头大尾
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode smallHead = new ListNode(0);
ListNode bigHead = new ListNode(0);
ListNode smallTail = smallHead;
ListNode bigTail = bigHead;
while (head != null){
if (head.val < x){
smallTail = smallTail.next = head;
}else
bigTail = bigTail.next = head;
head = head.next;
}
smallTail.next = bigHead.next;
bigTail.next = null;
return smallHead.next;
}
}
LeetCode 234 回文链表
快慢指针找到中点，从中点往后翻转
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
while(fast != null&& fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
if(fast != null)
slow = slow.next;
slow = reverse(slow);
fast = head;
while(slow != null){
if(fast.val != slow.val)
return false;
fast = fast.next;
slow = slow.next;
}
return true;
}
public ListNode reverse(ListNode head){
if(head == null|| head.next == null)
return head;
ListNode pre = null;
while(head != null){
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
LeetCode160 两个链表第一个公共节点
可以让长的先走，再找交点，简单点就AB相当于接在一起A走完走B，B走完走A，早晚会在交点相遇
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempA = headA;
ListNode tempB = headB;
while (tempA != tempB){
tempA = tempA == null ? headB : tempA.next;
tempB = tempB == null ? headA : tempB.next;
}
return tempA;
}
}
LeetCode24 两两交换链表节点
递归比较简单
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode third = swapPairs(head.next.next);
ListNode second = head.next;
head.next = third;
second.next = head;
return second;
}
}
LeetCode141&142环形链表以及入口节点
快慢指针
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode third = swapPairs(head.next.next);
ListNode second = head.next;
head.next = third;
second.next = head;
return second;
}
}
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (slow == fast){
while (head != slow){
head = head.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}
LeetCode19 删除链表倒数第N个节点
快慢指针，fast先走n步，在和slow同时走，slow删除后面的就OK
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head, slow = head;
for(int i = 0; i < n; i++){
fast = fast.next;
}
if(fast == null)
return head.next;
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}
LeetCode206 反转链表
弱智题
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
while(head != null){
ListNode next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
链表倒数第K个节点与上文删除基本相同
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode first = head;
ListNode second = head;
while (k-- > 0){
first = first.next;
}
while (first != null){
first = first.next;
second = second.next;
}
return second;
}
}
删除链表节点
双指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = head;
ListNode pre = dummy;
while (cur != null){
if (cur.val == val){
pre.next = cur.next;
break;
}
pre = cur;
cur = cur.next;
}
return dummy.next;
}
}
从尾到头打印链表
可以用栈，也可以先反转在遍历
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<>();
ListNode temp = head;
while (temp != null){
stack.push(temp);
temp = temp.next;
}
int size = stack.size();
int[] res = new int[size];
for (int i = 0; i < size; i++)
res[i] = stack.pop().val;
return res;
}
}
LeetCode1019 链表下一个更大节点
见到这种找接下来第一个比当前大的基本就是单调栈，栈底到栈顶逐渐变小
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public int[] nextLargerNodes(ListNode head) {
List<Integer> list = new ArrayList<>();
while (head != null){
list.add(head.val);
head = head.next;
}
Stack<Integer> stack = new Stack<>();
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++){
while (!stack.empty() && list.get(stack.peek()) < list.get(i)){
int index = stack.pop();
res[index] = list.get(i);
}
stack.push(i);
}
return res;
}
}
LeetCode21 合并两个有序链表
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null || list2 == null)
return list1 == null? list2: list1;
ListNode first = (list1.val < list2.val)? list1: list2;
first.next = mergeTwoLists(first.next, first == list1? list2: list1);
return first;
}
}
若有收获，就点个赞吧
0 人点赞
