Reverse LinkedList
方法1:三个指针
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode prev = null;
ListNode curr = head;
ListNode next;
while(curr != null){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
方法2:设置虚拟头结点，然后从头遍历原来的链表，每次都把原链表的节点插入到dummyHead后面。
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode dummyHead = new ListNode(-1);
ListNode curr = head;
while(curr != null){
ListNode next = curr.next;
curr.next = dummyHead.next;
dummyHead.next = curr;
curr = next;
}
return dummyHead.next;
}
Reverse LinkedList II
方法1：基于上面的三指针法，注意把需要保存的节点都保存一下
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode prevHead = null;
int i = 1;
ListNode curr = head;
while(i<m){
prevHead = curr;
curr = curr.next;
i++;
}
ListNode prev = null;
ListNode next = null;
ListNode reverseTail = curr;
while(i<=n){
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
i++;
}
reverseTail.next = curr;
if(prevHead != null){
prevHead.next = prev;
return head;
}else{
return prev;
}
}
方法2：基于虚拟头结点
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
int i;
//找到反转部分的dummyHead
for(i = 0; i < m - 1; i ++){
dummyHead = dummyHead.next;
}
ListNode reverseTail = dummyHead.next;
ListNode curr = dummyHead.next;
ListNode next;
while(i < n){
next = curr.next;
curr.next = dummyHead.next;
dummyHead.next = curr;
curr = next;
i++;
}
reverseTail.next = curr;
if(reverseTail != head){
return head;
}else{
return dummyHead.next;
}
}
Remove Duplicates from Sorted List
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return null;
}
ListNode prev = head;
ListNode curr = head.next;
while(curr != null){
if(prev.val == curr.val){
ListNode delNode = curr;
prev.next = delNode.next;
curr = delNode.next;
delNode.next = null;
}else{
prev = curr;
curr = curr.next;
}
}
return head;
}
Partition List
public ListNode partition(ListNode head, int x) {
ListNode lessDummyHead = new ListNode(-1);
ListNode moreDummyHead = new ListNode(-1);
ListNode curr = head;
ListNode moreCurr = moreDummyHead;
ListNode lessCurr = lessDummyHead;
while(curr != null){
ListNode next = curr.next;
if(curr.val < x){
lessCurr.next = curr;
lessCurr = lessCurr.next;
}else{
moreCurr.next = curr;
moreCurr = moreCurr.next;
}
curr = next;
}
lessCurr.next = moreDummyHead.next;
moreCurr.next = null;
return lessDummyHead.next;
}
Odd Even Linked List
public ListNode oddEvenList(ListNode head) {
ListNode oddDummyHead = new ListNode(-1);
ListNode evenDummyHead = new ListNode(-1);
ListNode evenCurr = evenDummyHead;
ListNode curr = head;
int i = 1;
while(curr != null){
ListNode next = curr.next;
if((i & 1) == 1){
oddDummyHead.next = curr;
oddDummyHead = oddDummyHead.next;
}else{
evenCurr.next = curr;
evenCurr = evenCurr.next;
}
curr = curr.next;
i++;
}
oddDummyHead.next = evenDummyHead.next;
evenCurr.next = null;
return head;
}
Add Two Numbers
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode curr1 = l1;
ListNode curr2 = l2;
ListNode newHead = new ListNode(0);
ListNode curr =newHead;
int carry = 0;
while(curr1!= null || curr2 != null){
int x = curr1!=null?curr1.val:0;
int y = curr2!=null?curr2.val:0;
int sum = x + y + carry;
carry =sum/10;
curr.next = new ListNode(sum%10);
curr = curr.next;
if(curr1 != null)curr1 = curr1.next;
if(curr2 != null)curr2 = curr2.next;
}
if(carry == 1){
curr.next =new ListNode(1);
}
return newHead.next;
}
Add Two NumbersII
这题可以不停手动reverse，但是用栈更美观一些感觉....
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
ListNode curr1 = l1;
ListNode curr2 = l2;
while(curr1 != null){
s1.push(curr1.val);
curr1 = curr1.next;
}
while(curr2 != null){
s2.push(curr2.val);
curr2 = curr2.next;
}
ListNode dummyHead = new ListNode(0);
int carry = 0;
ListNode curr = dummyHead;
Stack<Integer> s = new Stack<>();
while((!s1.isEmpty()) || (!s2.isEmpty())){
int x = s1.isEmpty()?0:s1.pop();
int y = s2.isEmpty()?0:s2.pop();
int sum = x + y + carry;
carry = sum/10;
s.push(sum%10);
}
if(carry == 1){
s.push(1);
}
while(!s.isEmpty()){
curr.next = new ListNode(s.pop());
curr = curr.next;
}
return dummyHead.next;
}
Remove Linked List Elements
设置虚拟头结点，这是链表中的常用的技巧，否则如果第一个节点满足条件，不使用dummyHead，那将需要对头结点特殊处理。
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode prev = dummyHead;
while(prev!=null){
ListNode curr = prev.next;
if(curr!=null && curr.val == val){
prev.next = curr.next;
curr.next = null;
}else{
prev = prev.next;
}
}
return dummyHead.next;
}
Remove Dumplicates from Sorted List
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return null;
}
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode prev = dummyHead;
ListNode curr = head;
while(curr != null){
ListNode next = curr.next;
if(next != null && next.val == curr.val){
while(next != null && next.val == curr.val){
ListNode delNode = next;
curr.next = delNode.next;
next = next.next;
delNode.next = null;
}
prev.next = next;
}else{
prev = curr;
}
curr = next;
}
return dummyHead.next;
}
Swap Nodes In Pairs
public ListNode swapPairs(ListNode head) {
if(head == null){
return null;
}
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode p = dummyHead;
while(p != null && p.next != null){
ListNode node1 = p.next;
if(node1.next == null){
break;
}
ListNode node2 = node1.next;
ListNode next = node2.next;
node2.next = node1;
node1.next = next;
p.next = node2;
p = node1;
}
return dummyHead.next;
}
Insertion Sort List
public ListNode insertionSortList(ListNode head) {
if(head == null){
return null;
}
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode originNode = head.next;
//把链表分割成两部分
head.next = null;
while(originNode != null){
ListNode prevSorted = dummyHead;
ListNode newNode = originNode;
while(prevSorted.next != null && prevSorted.next.val <= newNode.val){
prevSorted = prevSorted.next;
}
originNode = originNode.next;
newNode.next = prevSorted.next;
prevSorted.next = newNode;
}
return dummyHead.next;
}
Remove Nth Node From End Of List
快慢指针法去找倒数第N个节点
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = dummyHead;
ListNode slow = dummyHead;
for(int i = 0; i < n; i ++){
fast = fast.next;
}
while(fast.next!=null){
fast = fast.next;
slow = slow.next;
}
ListNode delNode = slow.next;
slow.next = delNode.next;
delNode.next = null;
return dummyHead.next;
}
Rotate List
这个题画几个图就能明白题意，其实就是把倒数K个旋转一下，挪到前头去，但是需要注意的问题是，K有可能大于节点数，所以先遍历一遍，因为k可能大于链表节点数，所以遍历一次拿到节点总数，再用k去求余。然后可以直接循环length - k%length次拿到倒数第K+1个节点，然后进行相关的更改指向的操作就可以了。
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null || k == 0){
return head;
}
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode p = dummyHead;
int length = 0;
while(p.next!=null){
p = p.next;
length ++;
}
if(k%length == 0){
return head;
}
ListNode tail = p;
p = dummyHead;
for(int i = 0; i < length - k%length; i++){
p=p.next;
}
ListNode newHead = p.next;
p.next = null;
tail.next = dummyHead.next;
dummyHead.next = newHead;
return dummyHead.next;
}
还有 143 和 148 234
Middle of the Linked List
快慢指针法去找中间节点，还是加上dummyHead更好理解一些。慢的一次走一步，快的一次走两步，那么快的走过的路就是慢的的两倍。奇数和偶数个节点有不同的返回情况，画个图分析一下就可以了。
public ListNode middleNode(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = dummyHead;
ListNode slow = dummyHead;
while(fast != null && fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast == null){
return slow;
}
return slow.next;
}
