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

LeetCode 24:两两交换链表中的结点

程序员文章站 2022-05-06 11:01:30
...

题目描述:两两交换链表中的结点

说明: 关于链表的元素到底叫结点还是节点,请参考:

解题思路:

该题的关键是需要记录好交换前结点的头指针(即完成交换后的尾结点),可以引入一个填充结点prev,其next指针初始指向head结点,为方便迭代,声明一个临时指针tmp=prev,当tmp.next和tmp.next.next不为空,一直迭代,整个交换过程可以抽象为:
初始链表:
LeetCode 24:两两交换链表中的结点
(1)、声明指向前一个结点的指针start
LeetCode 24:两两交换链表中的结点
(2)、声明指向后一个结点的指针end
LeetCode 24:两两交换链表中的结点
(3)、处理链表头,将前置结点tmp的next指针指向end结点
LeetCode 24:两两交换链表中的结点
(4)、处理链表尾,将start的next指针指向end的next指针
LeetCode 24:两两交换链表中的结点
(5)、链表反转,将end的next指针指向start
LeetCode 24:两两交换链表中的结点
(6)、将tmp指针指向start
LeetCode 24:两两交换链表中的结点
依次类推:
参考代码如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode prev = new ListNode(0);
        prev.next = head;
        ListNode tmp = prev;
        ListNode start,end;
        while(tmp.next!=null && tmp.next.next!=null){
        	start = tmp.next;
        	end = start.next;
			tmp.next = end;
			start.next = end.next;
			end.next = start;
			tmp = start;
		}
		return prev.next;
    }
}

总结: 该题中引入一个前置的结点对解题有很大的帮助,这是链表题中重要的一种处理问题的思路。