给出一个长度为 n 的单链表和一个值 x ,单链表的每一个值为 listi ,请返回一个链表的头结点,要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧,并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。
题目解法:先找到链表的尾节点和链表的长度,判断节点数值是否大于给定值,是就插入到尾处。
可以使用虚拟的头结点对翻转过程进行简化,链表问题要考虑,极端值情况
public class Solution { /** * * @param head ListNode类 * @param x int整型 * @return ListNode类 */ public ListNode partition (ListNode head, int x) { // write code here if(head==null) return null; ListNode tail=null; ListNode temp=head; int len=1; while(temp.next!=null) { temp=temp.next; len++; } tail=temp; if(head==temp) return head; temp=new ListNode(Integer.MIN_VALUE); temp.next=head; ListNode head_temp=temp; ListNode temp_pre=temp; for(int i=0;i<=len;i++) { if(temp.val>=x) { temp_pre.next=temp.next; tail.next=temp; tail=temp; temp=temp.next; tail.next=null; continue; } temp_pre=temp; temp=temp.next; } return head_temp.next; } }