1721. 交换链表中的节点

朱雀 2023-10-05 21:25 5阅读 0赞

给你链表的头节点 `head` 和一个整数 `k` 。

**交换** 链表正数第 `k` 个节点和倒数第 `k` 个节点的值后，返回链表的头节点（链表 **从 1 开始索引**）。

**示例 1：**

![f6a823325939b5085f38a440585ac0f0.png][]

输入：head = [1,2,3,4,5], k = 2
    输出：[1,4,3,2,5]

**示例 2：**

输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
    输出：[7,9,6,6,8,7,3,0,9,5]

**示例 3：**

输入：head = [1], k = 1
    输出：[1]

**示例 4：**

输入：head = [1,2], k = 1
    输出：[2,1]

**示例 5：**

输入：head = [1,2,3], k = 2
    输出：[1,2,3]

**提示：**

*  链表中节点的数目是 `n`
 *  `1 <= k <= n <= 105`
 *  `0 <= Node.val <= 100`

package Solution1721;
    
    import java.util.Comparator;
    import java.util.PriorityQueue;
    import java.util.Stack;
    
    class Solution {
    	public ListNode swapNodes(ListNode head, int k) {
    		ListNode dummy1 = new ListNode(-1);
    		dummy1.next = head;
    		ListNode curr = head;
    		int count = 1;
    		int k1 = 0;
    		int k2 = 0;
    		while (curr != null) {
    			if (count == k) {
    				k1 = curr.val;
    			}
    
    			curr = curr.next;
    			count++;
    		}
    		int len = count;
    		curr = head;
    		count = 1;
    		while (curr != null) {
    			if (count == len - k) {
    				k2 = curr.val;
    			}
    
    			curr = curr.next;
    			count++;
    		}
    
    		curr = head;
    		count = 1;
    		while (curr != null) {
    			if (count == k) {
    				curr.val = k2;
    			}
    			if (count == len - k) {
    				curr.val = k1;
    			}
    
    			curr = curr.next;
    			count++;
    		}
    
    		return dummy1.next;
    
    	}
    
    	public ListNode reverseBetween(ListNode head, int left, int right) {
    		Stack<ListNode> stk = new Stack<ListNode>();
    
    		if (head == null || head.next == null)
    			return head;
    		ListNode dummy1 = new ListNode(-1);
    		ListNode s = dummy1;
    
    		ListNode dummy2 = new ListNode(-1);
    		ListNode b = dummy2;
    
    		ListNode curr = head;
    		int count = 1;
    		while (curr != null) {
    			if (count < left) {
    				s.next = curr;
    				s = s.next;
    			}
    			if (count > right) {
    				b.next = curr;
    				b = b.next;
    			}
    			if (count >= left && count <= right) {
    				stk.push(curr);
    
    			}
    
    			curr = curr.next;
    			count++;
    		}
    		b.next = null;
    		while (!stk.isEmpty()) {
    			s.next = stk.pop();
    			s = s.next;
    		}
    
    		s.next = dummy2.next;
    		return dummy1.next;
    
    	}
    
    	public ListNode partition(ListNode head, int x) {
    		if (head == null || head.next == null)
    			return head;
    		ListNode dummy1 = new ListNode(-1);
    		ListNode s = dummy1;
    
    		ListNode dummy2 = new ListNode(-1);
    		ListNode b = dummy2;
    
    		ListNode curr = head;
    		while (curr != null) {
    			if (curr.val < x) {
    				s.next = curr;
    				s = s.next;
    			} else {
    				b.next = curr;
    				b = b.next;
    			}
    			curr = curr.next;
    		}
    		b.next = null;
    		s.next = dummy2.next;
    		return dummy1.next;
    	}
    
    	public ListNode rotateRight(ListNode head, int k) {
    		if (head == null) {
    			return head;
    		}
    		if (k == 0) {
    			return head;
    		}
    
    		int count = 0;
    		ListNode start = head;
    		// traverse till the end of the list and keep incrementing
    		// count
    		while (head.next != null) {
    			head = head.next;
    			count++;
    		}
    		count++;
    		// if k > count, do k%count, its an optimization. 2%5 == 12%5
    		k = k % count;
    		// find the new k
    		k = Math.abs(count - k);
    		if (k == 0)
    			return start;
    		// connect last element to start
    		head.next = start;
    		// traverse for new k value
    		while (k-- > 0) {
    			head = head.next;
    		}
    		// note: head is not the last element, so set the start.
    		start = head.next;
    		head.next = null;
    		return start;
    	}
    
    	public ListNode mergeKLists(ListNode[] lists) {
    		if (lists == null || lists.length == 0)
    			return null;
    
    		PriorityQueue<ListNode> queue = new PriorityQueue<ListNode>(
    				(Comparator<? super ListNode>) new Comparator<ListNode>() {
    					public int compare(ListNode l1, ListNode l2) {
    						return l1.val - l2.val;
    					}
    				});
    
    		ListNode head = new ListNode(0);
    		ListNode p = head;
    
    		for (ListNode list : lists) {
    			if (list != null)
    				queue.offer(list);
    		}
    
    		while (!queue.isEmpty()) {
    			ListNode n = queue.poll();
    			p.next = n;
    			p = p.next;
    
    			if (n.next != null)
    				queue.offer(n.next);
    		}
    
    		return head.next;
    
    	}
    
    	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    		if (l1 == null)
    			return l2;
    		if (l2 == null)
    			return l1;
    		if (l1.val < l2.val) {
    			l1.next = mergeTwoLists(l1.next, l2);
    			return l1;
    		} else {
    			l2.next = mergeTwoLists(l1, l2.next);
    			return l2;
    		}
    	}
    
    	public ListNode removeElements(ListNode head, int val) {
    		ListNode header = new ListNode(-1);
    		header.next = head;
    		ListNode cur = header;
    		while (cur.next != null) {
    			if (cur.next.val == val) {
    				cur.next = cur.next.next;
    			} else {
    				cur = cur.next;
    			}
    		}
    		return header.next;
    	}
    
    	void printList(ListNode node) {
    		while (node != null) {
    			System.out.print(node.val + " ");
    			node = node.next;
    		}
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		ListNode head = new ListNode(1);
    		head.next = new ListNode(2);
    		head.next.next = new ListNode(3);
    		head.next.next.next = new ListNode(4);
    		head.next.next.next.next = new ListNode(5);
    		// head.next.next.next.next.next = new ListNode(2);
    
    		int k = 2;
    		sol.printList(sol.swapNodes(head, k));
    
    	}
    
    }

[f6a823325939b5085f38a440585ac0f0.png]: https://img-blog.csdnimg.cn/img_convert/f6a823325939b5085f38a440585ac0f0.png