L1-链表划分

Posted on | In |

给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。

你应该保留两部分内链表节点原有的相对顺序。

示例：

给定链表 1->4->3->2->5->2->null，并且 x=3

返回 1->2->2->4->3->5->null

法一

(1)遍历链表，将值大于给定值得结点插入新链表new_head
(2)将new_head与原链表连接
注意判断头结点是否为空 什么时候指针要后移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class ListNode {
	int val;
	ListNode next;

	ListNode(int x) {
		val = x;
		next = null;
	}
}
public class Solution {
    /**
     * @param head: The first node of linked list
     * @param x: An integer
     * @return: A ListNode
     */
		public ListNode partition(ListNode head, int x) {
		// write your code here
		ListNode p_cur = head, p_pre = null;
		ListNode new_head = null, new_end = null;
		while (p_cur != null) {
			if (p_cur.val >= x) {
				if (p_cur == head)
					head = head.next;
				else
					p_pre.next = p_cur.next;
				if (new_head == null)
					{new_head = p_cur;
					  new_end=p_cur;
					}
				else {
					new_end.next = p_cur;
					new_end = new_end.next;
				}
				 p_cur = p_cur.next; //注意不能少
			} else {
				p_pre = p_cur;
				p_cur = p_cur.next;
			}
		}
		if(new_head!=null)
		{
			if(head!=null)
				p_pre.next=new_head;
			else head=new_head;
			new_end.next=null;
			
		}
		
		return head;
	}
}

法二

参考链接:https://blog.csdn.net/supermuscleman/article/details/79330643