算法专题八： 链表

1.两数相加

题目链接：2. 两数相加 - 力扣（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 addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1=l1,cur2=l2;ListNode newHead = new ListNode(0);ListNode prev=newHead;int t=0;while(cur1!=null || cur2!=null || t!=0){if(cur1!=null){t+=cur1.val;cur1=cur1.next;}if(cur2!=null){t+=cur2.val;cur2=cur2.next;}prev.next=new ListNode(t % 10);prev=prev.next;t/=10;//如果有进位，使t为1，加入下次的计算}return newHead.next;}
}

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

题目链接：24. 两两交换链表中的节点 - 力扣（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 swapPairs(ListNode head) {if(head==null || head.next==null){return head;}ListNode newHead=new ListNode(0);newHead.next=head;ListNode prev=newHead;ListNode cur=prev.next;ListNode next=cur.next;ListNode nnext=next.next;while(cur!=null && next!=null){next.next=cur;cur.next=nnext;prev.next=next;prev=cur;cur=nnext;if(cur!=null){next=cur.next;}if(next!=null){nnext=next.next;}}return newHead.next;}
}

3.重排列表

题目链接：143. 重排链表 - 力扣（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 void reorderList(ListNode head) {if(head==null || head.next==null || head.next.next==null){return ;}// 找到中间的节点ListNode fast=head;ListNode slow=head;while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;}ListNode head2=new ListNode();ListNode cur=slow.next;slow.next=null;while(cur!=null){ListNode next=cur.next;    cur.next=head2.next;head2.next=cur;cur=next;  }// 合并两个列表ListNode cur1=head;ListNode cur2=head2.next;ListNode ret=new ListNode();ListNode prev=ret;while(cur1!=null){// 合并前一部分prev.next=cur1;prev=cur1;cur1=cur1.next;// 合并后一部分if(cur2!=null){prev.next=cur2;prev=cur2;cur2=cur2.next;}}}
}

4.合并k个升序列表

题目链接：23. 合并 K 个升序链表 - 力扣（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 mergeKLists(ListNode[] lists) {// 创建一个小顶堆，元素从小到大进行排列PriorityQueue<ListNode> heap=new PriorityQueue<>((v1,v2) -> v1.val - v2.val);for(ListNode l:lists){if(l!=null){heap.offer(l);}}ListNode ret=new ListNode(0);ListNode result=ret;while(!heap.isEmpty()){ListNode t=heap.poll();result.next=t;result=t;if(t.next!=null){heap.offer(t.next);}}return ret.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 mergeKLists(ListNode[] lists) {return mergeSort(lists,0,lists.length-1);}public ListNode mergeSort(ListNode[] lists,int left,int right){if(left>right){return null;}if(left==right){return lists[left];}int mid=(left+right)/2;ListNode l1=mergeSort(lists,left,mid);ListNode l2=mergeSort(lists,mid+1,right);// 把两个列表进行排序return mergeTwoList(l1,l2);}public ListNode mergeTwoList(ListNode l1,ListNode l2){if(l1==null){return l2;}if(l2==null){return l1;}ListNode newHead=new ListNode(0);ListNode cur1=l1, cur2=l2, result=newHead;while(cur1!=null && cur2!=null){if(cur1.val>cur2.val){result.next=cur2;result=cur2;cur2=cur2.next;}else{result.next=cur1;result=cur1;cur1=cur1.next;}}if(cur1!=null){result.next=cur1;}if(cur2!=null){result.next=cur2;}return newHead.next;}
}

5.K个一组列表翻转

题目链接：25. K 个一组翻转链表 - 力扣（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 reverseKGroup(ListNode head, int k) {ListNode cur=head;int n=0;while(cur!=null){cur=cur.next;n++;}n/=k;ListNode newHead=new ListNode(0);ListNode prev=newHead;cur=head;for(int i=0;i<n;i++){ListNode tmp=cur;for(int j=0;j<k;j++){ListNode ret=cur.next;cur.next=prev.next;prev.next=cur;cur=ret;}prev=tmp;}prev.next=cur;return newHead.next;}
}

 

希望对大家有所帮助！！！！