203. 移除链表元素

因为还得判断第一个元素是否等于val，所以我们加个头结点，然后用cur遍历，值为val就更改链表，否则继续移动

/*** 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 removeElements(ListNode head, int val) {ListNode h=new ListNode(0,head);ListNode cur=h;while(cur.next!=null){if(cur.next.val==val)cur.next=cur.next.next;else cur=cur.next;}     return h.next;}
}

707. 设计链表

class listnode{int val;listnode next;listnode(){}listnode(int val){this.val=val;}
}
class MyLinkedList {int len;listnode head;public MyLinkedList() {len=0;head=new listnode();}public int get(int index) {if(index<0||index>=len)return -1;listnode  cur=head.next;while(index>0){cur=cur.next;index--;}return cur.val;}public void addAtHead(int val) {len++;listnode n=new listnode(val);n.next=head.next;head.next=n;}public void addAtTail(int val) {listnode cur=head;while(cur.next!=null)cur=cur.next;listnode n=new listnode(val);cur.next=n;len++;}public void addAtIndex(int index, int val) {if(index<0||index>len)return;listnode n=new listnode(val);listnode cur=head;while(index>0){ cur=cur.next;index--;}n.next=cur.next;cur.next=n;len++;}public void deleteAtIndex(int index) {if(index<0||index>=len) return ;listnode cur=head;while(index>0){cur=cur.next;index--;}cur.next=cur.next.next;len--;}
}/*** Your MyLinkedList object will be instantiated and called as such:* MyLinkedList obj = new MyLinkedList();* int param_1 = obj.get(index);* obj.addAtHead(val);* obj.addAtTail(val);* obj.addAtIndex(index,val);* obj.deleteAtIndex(index);*/

206. 反转链表

用两个指针实现原地反转。

/*** 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 h=new ListNode();ListNode cur=head;ListNode last=head;while(last!=null){last=last.next;cur.next=h.next;h.next=cur;cur=last;}return h.next;}
}

24. 两两交换链表中的节点

/*** 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) {ListNode h=new ListNode();ListNode first,second,cur=h,last=head;while(last!=null){first=last;last=last.next;second=last;if(second==null){cur.next=first;break;}last=last.next;first.next=cur.next;second.next=first;cur.next=second;cur=first;}  return h.next;}
}

19. 删除链表的倒数第 N 个结点

/*** 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 h=new ListNode(0,head);ListNode cur=head;int len=0;while(cur!=null){cur=cur.next;len++;}int des=len-n;cur=h;while(des>0){cur=cur.next;des--;}cur.next=cur.next.next;return h.next;}
}

面试题 02.07. 链表相交

/*** 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 A=headA,B=headB;while (A != B) {A = A != null ? A.next : headB;B = B != null ? B.next : headA;}return A;}
}

142. 环形链表 II

/*** 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) {LinkedHashSet<ListNode> set = new LinkedHashSet<>();while(head!=null){if(set.contains(head))return head;set.add(head);head=head.next;}return null;}
}