我要招人

去企业版

首页 > 试题广场 >

交互链表节点

[编程题]交互链表节点

热度指数：13086 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

将给定的链表中每两个相邻的节点交换一次，返回链表的头指针
例如,
给出1->2->3->4，你应该返回链表2->1->4->3。
你给出的算法只能使用常量级的空间。你不能修改列表中的值，只能修改节点本身。

示例1

输入

{1,2}

输出

{2,1}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

Java

水中舟

import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
思路：将原链路表中head变成firstNode, head.next变成secondNode, 当新链表的preNode.next = secondNode; firstNode.next = secondNode.next;
secondNode.next = firstNode; preNode = firstNode; head = 此时的firstNode.next就是原secondNode.next
*/

public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode swapPairs (ListNode head) {
// 哑节点是用于返回的，哑节点的next要等于head是因为，当原链表只有一个节点的时候。要返回原链表的head
ListNode dummy = new ListNode(0);
dummy.next = head;
// 引用一个哑节点，用于新链表的头部
ListNode preNode = dummy;
//判断head及head.next，同时不为空，进入循环交换
while(head !=null && head.next != null) {
    ListNode firstNode = head;
    ListNode secondNode = head.next;

    preNode.next = secondNode;
    firstNode.next = secondNode.next;
    secondNode.next = firstNode;
            // preNode节点引用要跳到firstNode；而head要引用 firstNode.next，因为此时的firstNode.next就是原secondNode.next即当前head.next.next
            preNode = firstNode;
            head = firstNode.next;
}
return dummy.next;

}
}

发表于 2020-08-16 13:37:50 回复(0)

Java

就是很菜

public class Solution60 {

	public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null) {
        	return head;
        }
        //先将原来的链表交错分开成为两个链表
        ListNode cur1= head;
        ListNode cur2 = head.next;
        while(cur1!=null&&cur1.next!=null) {
        	ListNode secound = cur1.next;
        	cur1.next = secound.next;
        	secound.next = secound.next==null?null:secound.next.next;
        	cur1=cur1.next;
        }
        //然后将两个链表在合并到一起
        ListNode cur3 = head;
        ListNode cur4 = cur2;
        while(cur3!=null&&cur4!=null){
        	ListNode cur3Next = cur3.next;
        	ListNode cur4Next = cur4.next;
        	cur4.next = cur3;
        	cur4=cur4Next;
        	cur3.next=cur4;
        	cur3=cur3Next;
        } 
        //如果是奇数后面需要在加一位
        if(cur1!=null){
            ListNode node = cur2;
            while(node.next!=null){
                 node = node.next;
             }
            node.next = cur1;
        }
        return cur2;
    }
}

发表于 2020-05-10 19:27:07 回复(0)

Java

Mono_Chrome

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        ListNode pre = dummy;
        while (cur != null && cur.next != null) {
            ListNode pNext = cur.next;
            cur.next = pNext.next;
            pNext.next = cur;
            pre.next = pNext;
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

发表于 2019-11-05 19:06:58 回复(0)

Java

HW柯可

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode tmp, pre = dummy, cur = head;
        while(cur != null && cur.next != null){
            tmp = cur.next;
            cur.next = tmp.next;
            tmp.next = pre.next;
            pre.next = tmp;
            
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

发表于 2019-07-06 17:40:54 回复(0)

Java

木丶年华

//写的比较复杂，但思想简单

public ListNode swapPairs(ListNode head) {

if(head == null || head.next == null)
return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy, cur = head;
while(cur != null && cur.next != null){ //如果最后只有一个链点就直接返回，不需要交换
ListNode next = cur.next.next; //next判断是否是最后两个链表点
if(next != null){
pre.next = cur.next;
cur.next = next;
pre.next.next = cur;
pre = cur;
}else{
pre.next = cur.next;
pre.next.next = cur;
cur.next = null; //最后要置于null，不然尾部会形成循环
}
cur = cur.next;
}
return dummy.next;
}

发表于 2018-05-28 20:54:56 回复(0)

Java

AMMOK

public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)return head;
        
        ListNode p = new ListNode(0);
        ListNode result = p;
        p.next=head;
        ListNode p1=head;
        while(p1!=null&&p1.next!=null){
             //以下为交换相邻两个节点，实则考虑两个节点和前后各一个节点的指针问题
             // 相当于每一次循环对四个节点进行处理
            ListNode p2=p1.next;
            ListNode temp = p2.next;
            p.next=p1.next;
            p2.next=p1;
            p1.next=temp;
          //调整指针位置为了进入下一次循环  
            p=p.next.next;
            p1=p.next;
        }  //针对while中没处理的尾部剩一个节点的情况进行处理
           if(p1!=null){
            p1.next=null;
        }
         return result.next;       
    }
}

编辑于 2017-12-09 20:58:39 回复(0)

Java

Holiday_12138

public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode next = cur.next;
        while(next != null && next.next != null) {
            cur.next = next.next;
            next.next = cur.next.next;
            cur.next.next = next;
            cur = next;
            next = next.next;
        }
        return dummy.next;
    }
}

发表于 2017-06-03 16:38:12 回复(0)

Java

城市里的养猫者

public class Solution {
    public ListNode swapPairs(ListNode head) {
        
        if ((head == null)||(head.next == null))
            
            return head;
        ListNode n = head.
        ListNode n = head.next;
        head.
        head.next = swapPairs(head.next.next);
        n.
        n.next = head;
        
        return n;
    }
}
    }
}

发表于 2017-03-12 23:27:56 回复(0)

Java

詆調壹點

public class Solution {
    public static ListNode swapPairs(ListNode head) {
		if(head == null || head.next == null) return head;
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		for (ListNode pre = dummy, cur = head, temp; cur != null && cur.next != null; pre = cur, cur = cur.next) {
			temp = cur.next;
			cur.next = temp.next;
			temp.next = pre.next;
			pre.next = temp;
		}
		return dummy.next;
	}
}

发表于 2016-11-18 01:02:10 回复(0)