欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现-交换链表当中的两个节点

程序员文章站 2022-07-03 19:18:55
...

给你一个链表以及两个权值v1v2,交换链表中权值为v1v2的这两个节点。保证链表中节点权值各不相同,如果没有找到对应节点,那么什么也不用做。

 注意事项

你需要交换两个节点而不是改变节点的权值

样例

给出链表 1->2->3->4->null ,以及 v1 = 2 , v2 = 4

返回结果 1->4->3->2->null


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * @param head a ListNode
     * @oaram v1 an integer
     * @param v2 an integer
     * @return a new head of singly-linked list
     */
    public ListNode swapNodes(ListNode head, int v1, int v2) {
       ListNode dummy=new ListNode(0);
		dummy.next=head;
		ListNode node1Prev=null,node2Prev=null;
		ListNode cur=dummy;
		while(cur.next!=null){
			if(cur.next.val==v1){
				node1Prev=cur;
			}else if(cur.next.val==v2){
				node2Prev=cur;
			}
			cur=cur.next;
		}
		if(node1Prev==null||node2Prev==null)
			return head;
		if(node2Prev.next==node1Prev){
			ListNode t=node1Prev;
			node1Prev=node2Prev;
			node2Prev=t;
		}
		ListNode node1=node1Prev.next;
		ListNode node2=node2Prev.next;
		if(node1Prev.next==node2Prev){
			node1Prev.next=node2;
			node1.next=node2.next;
			node2.next=node1;
		}else{
			node1Prev.next=node1.next;
			node2Prev.next=node2.next;
			node2.next=node1Prev.next;
			node1Prev.next=node2;
			node1.next=node2Prev.next;
			node2Prev.next=node1;
		}
		return dummy.next;

    }
}